时间复杂度是衡量一个算法好坏的重要标准,拿排序算法来说,同样是排序可以选择时间复杂度为O(n^2)的冒泡排序,还可以选择O(nlogn)的快排(或归并排序),这样比较就明显发现快排算法肯定是优于冒泡排序的(两者都不涉及空间占用)
- 时间复杂度的分析是基本功,在算法竞赛中我们必须要依据题目给出的测试数据范围,来设计相应复杂度算法,这里就不在深入展开。在考研范围内我们要掌握的就是可以分析自己的伪码,还有题目中代码的复杂度
下面举几个比较简单的时间复杂度分析例子
- O(√n) 简单分析一下,跳出循环的条件是y^2级别的增长 | 增长到n 所以y^2<=n -》y<=√n
int y = 0;
while((y+1)*(y+1) <= n)
y += 1;
- (14 年统考真题) O(nlogn)
count = 0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;
- (17 年统考真题)
int func(int n){
int i = 0; sum = 0;
while(sum < n) sum += ++i;
}
- 解析:解释一下17年的真题 虽然不难但还是比较容易算错的,其实这题考的不是时间复杂度的分析,而是阅读代码的能力(是否理解前缀++)下面将源码拆分一下时间复杂度便一眼看出 | 跳出循环的条件为累加级别的增长(1+2+3+..+t) < n;简单的求和等差数列求和公式可以知道是 t^2 级别的增长 即同第一题 O(√n) 拆分代码如下
int func(int n){
int i = 0; sum = 0;
while(sum < n){
i++;
sum+=i;
}
}
- 小结:总体来说时间复杂度分析是送分题,但还要在掌握分析方法的同时还要细心
拓展:递归程序时间复杂度的分析
- 引例:斐波那契数列;后项是前两项的和
形如:1,1,2,3,5... f(1)=1,f(2)=1, f(n)=f(n-1)+f(n-2) - 递归程序 O(2^n)
int Fibo(int n){
if(n <= 0) return -1;
if(n == 1 || n == 2)
return 1;
return Fibo(n-1) + Fibo(n-2);
}
- 分析:对于递归程序的分析,我们要理解它具体是如何调用的;如上述程序对于任何一个大于2的整数,程序都会深入调用计算 前两位,就如同一个二叉树一样 每次调用都会分成两部分,最终总次数就是(2^0 + 2^1 + 2^2 + .. + 2^(n-1)) 等比数列求和 2^n - 1 所以最终的时间复杂度 O(2^n)
- 扩充:指数级别的时间复杂度是相当恐怖的,很容易导致堆栈溢出,所以对于上述问题我们可以采用记忆型递归(空间换时间) 或 递推公式求解
网友评论