时间复杂度的计算

执行次数T(n)是关于问题规模n的函数

常数阶

复杂度为O(1)

线性阶

int i;
for(i = 0 ; i < n ; i++){
    //代码
}

复杂度为O(n)

对数阶

int count = 1;
while(count < n){
  count = count * 2;
  //代码  
}

数学公式：2x = n --> x = log2n

因此这个循环的时间复杂度为O(logn)

平方阶

类型1：n*n

int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < n ; j++){
    //代码   
   }    
}

时间复杂度为O(n^2^)。

类型2：n*m

如果内层循环改成了m次，时间复杂度就为O(n*m)

int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < m ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}

类型3：特殊n*n

再来看一段程序，当内层循环j = i时

int i;
for(i = 0 ; i < n ; i++){
   for(j = i ; j < n ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}

i = 0时，内层循环执行了n次，

i = 1时，执行了n-1次,

i = n-1时，执行了1次，所以总的执行次数为：

n+(n-1)+(n-1)+...+1 = n(n+1)/2 = n^2^/2 + n/2

根据大O推导方法，保留最高阶项，n^2^/2 ，然后去掉这个项相乘的常数，1/2

因此，这段代码的时间复杂度为O(n^2^)

类型4：斐波那契数列

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。

通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n^，同时当 n > 4 时 T(n) >= (3/2)^n。

简化后为 O(2^n^)

常见的时间复杂度

时间复杂度所耗费的时间是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) <O(2^n^) < O(n!) <O(n^n^)