(01)王道数据结构-时间复杂度

算法1：逐步递增型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(3000);
    return 0;
}

void loveYou(int n) {  //n为问题规模   
    int i = 1;         //爱你的程度
    while (i <= n) {   //每次+1
        i++;
        printf("I Love You %d\n", i);
    }
    printf("I Love You More Than %d\n", n);
}

(一)代码分析：

(1)语句频度

第09行：执行了1次

第10行：执行了3001次

第11行：执行了3000次

第12行：执行了3000次

第14行：执行了1次

T(3000) = 1 + 3001 + 2*3000 + 1

(2)时间复杂度

时间开销与问题规模n之间的关系

T(n) = 3n + 3

实际上时间复杂度只考虑阶数高的部分，高阶的常数项可以忽略

故本代码时间复杂度为: T(n) = n

(二)运算规则

$$ \begin{align*} &(a)加法规则:T_n = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n))) \\ &(b)乘法规则:T_n = T_1(n) \times T_2(n) = O(f(n)) \times O(g(n)) = O((f(n) \times g(n))) \end{align*} $$

(三)时间复杂度排序

$$ \begin{align*} O(1) < O(log_2n < O(n)<O(nlog_2n<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) \end{align*} $$

记忆口诀：常对幂指阶

算法2：嵌套循环型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(5);
    return 0;
}

void loveYou(int n) {  //n为问题规模   
    int i = 1;         //爱你的程度
    while (i <= n) {   //每次+1
        i++;
        printf("I Love You %d\n", i);
        for (int j = 1; j <= n; j++) { //嵌套循环两层
            printf("I am Iron Man\n");//内层循环共执行n*n次
        }
    }
    printf("I Love You More Than %d\n", n);
}

$$ 时间复杂度：T(n) = O(n) + O(n^2) = O(n^2) $$

结论：

(1)顺序执行的代码只会影响常数项，可以忽略

(2)只需要挑循环中的一个基本操作分析它的执行次数与n的关系即可

(3)如果有多层循环嵌套，只需关注最深层循环循环了几次

算法3：指数递增型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(100);
    return 0;
}

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);
}

时间复杂度分析：

(1)最深层语句频度为x

(2)循环结束时满足:

$$ 2^x>n \rightarrow x = log_2n + 1 $$

(3)时间复杂度:

$$ T(n) = O(x) = O(log_2n) $$

算法4：搜索数字型爱你

#include<stdio.h>
void loveYou(int flag[], int n);
int main(void) {
    int flag[] = {1,2,3,4,5,6,7,8,9};
    loveYou(flag,5);
    return 0;
}

void loveYou(int flag[], int n) {  //n为问题规模   
    printf("I Am Iron Man\n");
    for (int i = 0; i < n; i++) {
        if (flag[i] == n) {
            printf("I Love You %d\n", i);
            break;
        }
    }
}