什么是时间复杂度
算法的时间复杂度,也称为算法的时间量度,记作:T(n) = O(f(n)),也成为大O记法.
复杂度随n增大而增大,算法的执行时间的增长率和f(n)的增长率相同,所以也就称之为时间复杂度
如何分析时间复杂度
用几个通俗好懂的栗子来解释,包含常用的几种时间复杂度
先剥开第一个栗子~
int sum = 0,n = 100; /*执行一次*/
sum = (1+ n) * n / 2; /*执行一次*/
printf("d%, sum); /*执行一次*/
f(n) = 3 那么时间复杂度等于O(3)吗?
答案是 不等于
接下来我们用推导大O阶的第一个法则来解释:
1.用常数1取代运行时间中的所有加法常数
f(n)中加法常数等于3 也就是改成 f(n) = 1
接下来推导大O阶的第二个法则
2.在修改后的运行次数函数中,只保留最高阶项
上面例子中,没有最高阶,所以这个算法的时间复杂度是O(1)
即使 我们的代码中有 几十句 sum = (1+ n) * n / 2;
他们的区别也只是执行一次和执行几十次的区别,因为他的执行次数是恒定的,也就是固定的,不会随着n的变大有任何改变,不包含在循环结构中,复杂度也仍然是O(1).
与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶
再来剥开第二个栗子~
int i;
for(i = 0; i < n;i++){
printf("里面执行时间复杂度为O(1)的程序步骤序列");
}
推导大O阶层:f(n) = n 它的时间复杂度是 O(n),也称之为线性阶
如果改成
int i;
for(i = 0; i < 2;i++){
for(i = 0; i < n;i++){
printf("里面执行时间复杂度为O(1)的程序步骤序列");
}
}
推导大O阶层:f(n) = 2n 那么时间复杂度等于O(2n)吗
答案也是 不等于!!
接下我们用推导大O阶的第三个法则也是本文要提到的最后一个法则:
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数.得到的结果就是大n阶
上面的栗子中最高阶项等于2,去除这个常数也就是改过之后的带代码的时间复杂度仍然是O(n)
接下来让我们拿出第三个栗子
int count = 1;
while(count < n){
count = count * 2; //时间复杂度为O(1)的程序步骤序列
}
由于每次乘以2之后,就距离n更近了一分.也就是有多少2相乘后大于n,就会推出循环.有2^x(2的x次幂) = n ,得到x = log2(n),所以时间复杂度是 O(log n)也称之为对数阶
ok,第四个栗子
int i,j;
for (i = 0, i < n; i++){
for(j = 0; j < n; j++){
printf("里面执行时间复杂度为O(1)的程序步骤序列");
}
}
内层循环的时间复杂度是O(n),上面已经计算过了,而外面还嵌套循环了n次.所以时间复杂度是O(n^2), 也称之为平方阶
由此得出结论,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数.
好,下面我们来修改一下上面的栗子
int i,j;
for (i = 0, i < n; i++){
for(j = i ; j < n; j++){ /*注意 j = i 而不是 0*/
printf("里面执行时间复杂度为O(1)的程序步骤序列");
}
}
当i=0时,内循环执行n次,i=1时,执行了n-1次,....当i = n - 1时,执行了1次.所以总得执行次数是
根据上面我们提到的三条推导大O阶的规则,1.没有加法常数,过. 2.只保留最高阶,得到(n^2 )/ 2 . 3.去掉最高阶相乘的常数,得到n^2,所以时间复杂度是 O(n^2)
总结
以上列出了几种常用的时间复杂度的计算和三项基本规则,看起来并不是很难理解,对吧~
常用时间复杂度所耗费的时间从小到大依次是:
O(1) < O(log n) < O(n) < O(n log n) < O(n ^2) <O(n ^3) <O(2 ^n) <O(n!) <O(n ^n)
常用的算法时间复杂度一般在O(n ^2)之前.
最后
此篇文章是 程杰的《大话数据结构》中算法一章提到的例子和解释,我仅根据自己的理解和思路整理出来一些重要的我认为重要的部分记录下来,如有理解错误,还希望大家能够帮忙指出.
另,此书讲解很细致,也很通俗,感兴趣的同学可以阅读实践~
