时间复杂度(分析程序效率)

关于时间复杂度，参看http://blog.csdn.net/zhuchzhi/archive/2007/03/14/1529514.aspx

总结如下：

1、如果函数中没有n，也就是语句执行的次数是恒定的，则可知时间复杂度为O(1)

2、如果函数中有n,但是不知道执行的次数，可以这样做：假设执行次数为m，经过m次执行后条件参数变为x<=100(假设)，只需让x = 100,解除m即可，然后转成O().

3、如何判断两个时间复杂度的高低？比如一个是O(x)=f(n),另一个是O(y)=g(n)，通过两个式子相除，如果为常数则两个时间复杂度一样；若比值>1且常数增长，则O(x)比O(y)增长得快些，即高效性：O(x)<O(y)；反正亦然。

4、复杂度关系：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!

例如：

x = 1;
while(x<n){

x*=2;

}

解：设执行次数为m，则m次后x=2^m,然后看循环条件x<n，也就是说最后x=n-1，而后推出循环。所以，n-1=2^m，解出m=根号(n-1) = (n-1)^1/2(0.5次方)