定义
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大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) |
网友评论