程序效率问题？

Question

求第一个无重复字符,如"total"的第一个无重复字符是o,"teeter"的第一个无重复字符是r,效率要优于O(n的平方) 
public static Character FirstNonRepeated(String)
其中效率要优于O(n的平方) 
是什么意思？

Answer 1

就是算法的时间复杂度在最坏情况下，要小于O(n的平方)
分析复杂度时，主要考察算法中的重要操作（费时），如赋值，比较等。
O()是算法复杂度的上界。就是算法运行时间必然小于等于O()。
e.g.//不考虑程序的实际意义，只需分析赋值操作即可。
int sum=0;  //只赋值1次
for(int i=0;i<n;i++)    //i=0赋值1次，i++赋值n次
   for(int j=0;j<n;j++) //j=0赋值n次，j++赋值n*n次
      sum=sum+j;        //赋值n*n次。 则这个算法的复杂度应该等于2*n*n+2n+2 <=O(n*n)。
这是详细过程，通常只要分析循环内的表达式就行。

Answer 2

已经问过了
http://topic.csdn.net/u/20090513/17/43abdcf7-7db8-4a0e-bd6a-3cb53c7e7f6d.html