一、时间复杂度案例
时间复杂度-事前预估算法时间开销与问题规模的关系
算法1：逐步递增型
// 算法1：逐步递增型
void loveYou(int n)
{
int i = 1; // 执行一次
while (i <= n) // 执行3001次
{
i++;
printf("I Love You %d\n", i); // 执行3000次
}
printf("I love you more than %d\n", n); //执行1次
}
int main()
{
int n = 10;
loveYou(n);
return 0;
}以下是部分代码执行结果：
注意点：这里判断语句while要比printf()多执行一句，时间复杂度T（3000）= 1+3001+2*3000+1，用大O表示法：T(n) = O(n)。
算法2：嵌套循环型
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>、
// 算法2：嵌套循环型
void loveYou(int n)
{
int i = 1; // 执行一次
int count = 0;
while (i <= n) // 外层执行n次
{
i++;
printf("I Love You %d\n", i);
for (int j = 1; j <= n; j++)
{
printf("I am Iron Man\n"); // 内层循环执行n*n
count++;
}
}
printf("I love you more than %d\n", n);
printf("count=%d\n", count);
}
int main()
{
int n = 10;
loveYou(n);
return 0;
}以下是部分代码执行结果：
注意点：这里的时间规模T(n) = O(n) + O(n2) = O(n2)
算法3：指数递增型
#include <stdio.h>
// 算法3：指数递增型
void loveYou(int n)
{
int i = 1; // 执行一次
int count = 0;
while (i <= n) // 外层执行n次
{
i = i*2; //每次翻倍
printf("I Love You %d\n", i);
count++;
}
printf("I love you more than %d\n", n);
printf("count=%d\n", count);
}
int main()
{
int n = 100;
loveYou(n);
return 0;
}以下是部分代码执行结果：
计算上述时间复杂度T(n)：
设最深层循环的语句频度（总共循环的次数）为 x，（这里相当于x个2相乘）
由循环条件可知，循环结束时 2x > n 跳出循环
x > log2n
x是执行次数， 所以 x = log2n+1 跳出循环
综上所述：时间复杂度T(n) = O(x) = O(logn)
算法4 ：数字搜索型
情形1：最好的时间复杂度（n = 1）
void loveYou(int flag[],int n)
{
int i = 0; // 执行一次
int count = 0;
printf("I am a superman %d\n");
for (int i = 0; i < n;i++)
{
if (flag[i] == n)
{
printf("I love you %d\n");
break;
}
count++;
}
printf("count=%d\n", count);
}
int main()
{
int flag[10] = { 1,2,3,4,5,6,7,8,9,10 };
int n = 1;
loveYou(flag,n);
return 0;
}以下是执行结果：
情形2：最坏时间复杂度（ n = 10）
以下是执行结果：
情形3：平均复杂度（元素n在任意一个位置的概率相同，即1/n）
循环次数X = (1+2+3+……+n) * 1/n = （1+n)/2
关于数据结构中时间复杂度汇总
| 算法类型 | 时间复杂度 | 备注 |
|---|---|---|
| 线性查找 | (O(n)) | 顺序查找 |
| 二分查找 | (O(\log n)) | 仅适用于有序数组 |
| 冒泡排序 | (O(n^2)) | 最好情况 (O(n))（提前终止） |
| 插入排序 | (O(n^2)) | 最好情况 (O(n))（近乎有序） |
| 快速排序 | 平均 (O(n \log n))，最坏 (O(n^2)) | 基于分治，常用且高效 |
| 归并排序 | (O(n \log n)) | 稳定排序，空间复杂度 (O(n)) |
| 堆排序 | (O(n \log n)) | 原地排序（空间 (O(1))） |
| Floyd-Warshall | (O(n^3)) | 多源最短路径 |
| 斐波那契递归 | (O(2^n)) | 低效，可用迭代优化为 (O(n)) |
关于时间复杂度的几个结论
- 结论1：可以只考虑阶数高的部分
- 结论2：问题规模足够大时，常数项系数也可以忽略
- 结论3：加法规则-只保留高阶项
- 结论4：乘法规则-都保留
- 结论5：顺序执行的代码只会影响常数项，可以忽略
- 结论6：只需要挑循环中的一个基本操作分析它的执行次数与问题规模n之间的关系即可
- 结论7：如果有多层嵌套循环，只需关注最深层循环了几次
- 结论8：算法的性能问题只有在问题规模n很大的时候才会暴露出来
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
评论列表（1条）
好厉害的一个网站
