时间复杂度计算

定义

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

常数阶

int sum = 0,n = 100;
sum = (1 + n)*n/100;

时间复杂度为O(1)。

线性阶

sum = 0;
for(int i = 1; i <= n; i ++){
    sum += i;
}

循环体中的代码必须执行n次，循环的时间复杂度为O(n)。

对数阶

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

x个2相乘大于n后，就会推出循环。由2^x=n，得到x = log2n。
所以这个循环体的时间复杂度为O(logn)。

平方阶

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

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

常见的时间复杂度

执行次数函数	阶
12	O(1)
n+9	O(n)
2n^2+3n+9	O(n^2)
3log2n+8	O(logn)
4n+3nlog2n+8	O(nlogn)
7n^3 + 3n^2 + 6n+5	O(n^3)
2^n	O(2^n)