算法：时间复杂度从新认识


		定义：
1.时间频度：
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
 
例如：
[java] 
for(int i = 0 ; i < 10 ; i++){  
    //执行语句  
}  
 
那么上面的执行语句会执行10次，那么他的时间频度 T（n） = 10；
 
2.时间复杂度：
时间频度变化时呈现的规律。
按数量级递增排列，常见的时间复杂度有：
    常数阶O(1),对数阶O(log2n),线性阶O(n),
    线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，
    k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
例如：
[java] 
举几个具体的例子：  
1.  
for i:=1 to 100 do for j:=1 to 100 do s[i,j]:=0;  
执行次数100*100次，时间复杂度O(1)  
2.  
for i:=1 to n do for j:=1 to 200 do s[i,j]:=0;  
执行次数n*200次，时间复杂度O(n)  
2.  
for i:=1 to n do for j:=1 to n div 2 do s[i,j]:=0;  
执行次数n*n/2次，时间复杂度O(n^2)  
3.  
for i:=1 to n do for j:=1 to n-1 do for k:=1 to n-2 do s[i,j,k]:=0;  
执行次数n*(n-1)*(n-2)次，时间复杂度O(n^3)  
4.  
for i:=1 to n do  
  begin  
    for j:=1 to n do s[i,j,0]:=0;  
    for j:=1 to n do for k:=1 to n do s[i,j,k]:=1;  
  end;  
执行次数n*(n+n*n)次，时间复杂度O(n^3)  
[java] 
追问没看懂举得例子。  
第一个例子不应该是O（10000）吗？  
第二个例子不应该是O（n*n/2）吗  
括号里面的数是怎么得来的啊？  
回答O(10000)和O(1)都是常数阶，所以O(10000)可以近似看成O(1)。  
O(n*n/2)和O(n^2)都是平方阶，所以O(n*n/2)可以近似看成O(n^2)。  
一个算法在计算机上的执行效率，主要看这个算法的时间复杂度是属于哪一阶的，常数的影响并不大。当n非常大时，O(10000)的算法和O(1)的算法执行的时间差不多，O(n*n/2)的算法和O(n^2)的算法执行的时间差不多，但是O(n*n/2)的算法会比O(10000)的算法慢很多。

补充：软件开发 , Java ,