江小南

V1

2023/02/02阅读:27主题:萌绿

【数据结构】时间复杂度

阅读本文,需要对算法的基本概念有所了解,可以阅读以下文章进行学习。

【数据结构】算法的基本概念

1. 算法效率的度量

2. 时间复杂度

时间复杂度是指算法中所有语句的频度(执行次数)之和。记为:

T(n)=O(f(n))

其中,n是问题的规模;f(n)是问题规模n的某个函数。(T为“time”的意思。)

随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同(正相关)。

运算规则

  1. 加法规则

多项相加,只保留最高阶的项,且系数变为1。

  1. 乘法规则

多项相乘,都保留。

注意

实际使用中,我们只关注循环的部分,用循环的部分来判断时间复杂度

  1. 顺序执行的代码只会影响常数项,可以忽略。
  2. 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。
  3. 如果有多层循环嵌套,只需关注最深层循环的循环次数。
  4. 时间复杂度计算忽略高阶项系数和低阶项。

常见的时间复杂度

最高阶数越小,说明算法的时间性能越好。

记忆口诀:常对幂指阶

示例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. 三种时间复杂度

  1. 最坏时间复杂度:最坏情况下算法的时间复杂度。
  2. 平均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间。
  3. 最好时间复杂度:最好情况下算法的时间复杂度。

4. 小结

分类:

后端

标签:

数据结构与算法

作者介绍

江小南
V1