江
江小南
V1
2023/02/02阅读:27主题:萌绿
【数据结构】时间复杂度
阅读本文,需要对算法的基本概念有所了解,可以阅读以下文章进行学习。
1. 算法效率的度量

2. 时间复杂度
时间复杂度是指算法中所有语句的频度(执行次数)之和。记为:
T(n)=O(f(n))
其中,n是问题的规模;f(n)是问题规模n的某个函数。(T为“time”的意思。)
随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同(正相关)。
运算规则
-
加法规则
多项相加,只保留最高阶的项,且系数变为1。
-
乘法规则
多项相乘,都保留。
注意
实际使用中,我们只关注循环的部分,用循环的部分来判断时间复杂度。
-
顺序执行的代码只会影响常数项,可以忽略。 -
只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。 -
如果有多层循环嵌套,只需关注最深层循环的循环次数。 -
时间复杂度计算忽略高阶项系数和低阶项。
常见的时间复杂度
最高阶数越小,说明算法的时间性能越好。

记忆口诀:常对幂指阶。
示例1
#include <stdio.h>
// 逐步递增型爱你
void loveyou(int n){ // n为问题规模
int i=1; // 爱你的程度
while (i<=n){
i++; // 每次加1
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
int main() {
loveyou(3000);
return 0;
}
F:\Computer\Project\practice\23\1-time\cmake-build-debug\1_time.exe
I Love You 2
...
I Love You 3000
I Love You 3001
I Love You More Than 3000
进程已结束,退出代码为 0

分析:
语句频度:
1:1次
2:3001次
3、4:3000次
5:1次
T(3000)=1+3001+2*3000+1
所以T(n)=3n+3=O(n)
这里实际上是算出了所有语句的执行频度,但是因为1和5影响常数项,属于低阶项。循环部分是高阶项,算出来是3n,但是忽略高阶项系数,最终结果为n。
示例2
#include <stdio.h>
// 嵌套循环型爱你
void loveYou(int n){ // n为问题规模
int i=1; // 爱你的程度
while (i<=n){
i++; // 每次加1
printf("I Love You %d\n",i);
for(int j=1;j<=n;j++){ // 嵌套两层循环,执行了n平方次
printf("I am Iron Man\n");
}
}
}
int main() {
loveYou(3000);
return 0;
}
分析:分析方法和示例1相同。我们这里直接给出结论。
外层循环每执行一次,内层循环就要执行一遍完整的问题规模。所以时间开销与问题规模的关系为:

同样的,最终我们只看最高阶项,忽略了最高阶项系数和低阶项。
示例3
#include <stdio.h>
// 指数递增型爱你
void loveYou(int n){ // n为问题规模
int i=1; // 爱你的程度
while (i<=n){
i=i*2; // 每次翻倍
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
int main() {
loveYou(3000);
return 0;
}
F:\Computer\Project\practice\23\3-time\cmake-build-debug\3_time.exe
I Love You 2
I Love You 4
...
I Love You 4096
I Love You More Than 3000
进程已结束,退出代码为 0
分析:
这个算法不能直观得出答案。
示例4
#include <stdio.h>
// 搜索数字型爱你
void loveYou(int flag[],int n){ // n为问题规模
printf("I Am Iron Man\n");
int count=1;
for(int i=1;i<=10;i++){ // 从第一个元素开始查找
count++;
if(flag[i]==n){ // 找到元素n
printf("count=%d\n",count);
printf("I Love You %d\n",n);
break; // 找到后立即跳出循环
}
}
}
int main() {
int flag[10]={1,7,3,4,10,6,2,8,9,5}; // 数据中乱序放了1~n的数
loveYou(flag,5);
return 0;
}
F:\Computer\Project\practice\23\4-time\cmake-build-debug\4_time.exe
I Am Iron Man
count=10
I Love You 5
进程已结束,退出代码为 0
分析:这个示例中循环语句被执行了10次,因为数据的最后一个元素才是5,符合条件。这也就引出了三种时间复杂度。
3. 三种时间复杂度
-
最坏时间复杂度:最坏情况下算法的时间复杂度。 -
平均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间。 -
最好时间复杂度:最好情况下算法的时间复杂度。
4. 小结

作者介绍
江
江小南
V1