【数据结构】时间复杂度

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

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

1. 算法效率的度量

2. 时间复杂度

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

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

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

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

运算规则

1. 加法规则

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

2. 乘法规则

多项相乘，都保留。

注意

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

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. 小结