1.2.2 算法效率的度量.md

↩返回主页

⬅上一节 / 下一节➡

---

1.2.2 算法效率的度量

  从上一节也能了解到，好的算法必须要求高效率与低存储量需求，所以我们在 时间复杂度 和 空间复杂度 对算法的效率作度量。

• 时间复杂度

  • 让算法先运行，事后统计运行时间？不可！存在的问题如下：

    • 算法和机器性能有关，如：超级计算机 v.s. 单片机

    • 算法和编程语言有关，越高级的语言执行效率越低

    • 算法和编译程序产生的机器指令质量有关

    • 有些算法是不能事后再统计的，如：导弹控制算法

    结论： 在评价一个算法时间开销的优劣时，排除与算法本身无关的外界因素，且不能用事后再评判。

  • 算法时间复杂度：事前预估算法时间开销 T(n) 与问题规模 n 的关系（T 表示 time）

  ---

  • 例子 1——循环案例：

    // 算法一：逐步递增型爱你
    // n 为问题的规模
    void loveYou(int 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);
    }

    • 语句频度：

      ①    --  1次
      ②    --  3001次
      ③④   --  3000次
      ⑤    --  1次
      
      T(3000) = 1 + 3001 + 2*3000 + 1
      

      时间开销与问题规模 n 的关系为：T(n) = 3n + 3

  • 当 n 足够大时，我们只需要考虑阶数最高的项即可

  • 大 O 表示法：大 O 表示“同阶”、同等数量级。如 T₁(n) = O(n)、T₂(n) = O(n²)、T₃(n) = O(n³)

    • 加法规则：多项相加，只保留最高阶的项，且系数变为 1

      T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(m)))

    • 乘法规则：多项相乘，都保留

      T(n) = T₁(n) × T₂(n) = O(f(n)) × O(g(n)) = O(f(n) × g(m))

      eg: T₃(n) = n³ + n²log₂n = O(n³) + O(n²log₂n) = O(n³)

    • O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

  • 根据大 O 表示法，上述算法例子 T(n) = 3n + 3 = O(n)

  ---

  • 例子 2——嵌套循环

    // 算法 2——嵌套循环
    // n 为问题的规模
    void loveYou(int n) {
        int i = 1;
        while(i <= n) {
            i++;
            printf("I Love You %d\n", i);
            for(int j; j<=n; j++) {
                printf("I am Iron Man\n");
            }
        }
        printf("I Love You More Than %d\n", n);
    }

    时间开销与问题规模 n 的关系：T(n) = O(n) + O(n²) = O(n²)

  • 例子 2——结论：

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

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

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

  ---

  • 例子 3——指数递增型

    // 算法 3——指数递增型
    // n 为问题的规模
    void loveYou(int 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);
    }

    设循环次数为 x，则，循环结束时，x 满足：2^x > n

    即，x = log₂n + 1

    T(n) = O(x) = O(log₂n)

  ---

  • 例子 4——搜索数字型

    // 算法 4——搜索数字型
    // n 为问题的规模
    void loveYou(int flag[], int 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;
            }
        }
    }

    最好情况（最好时间复杂度）：元素 n 在第一个位置，T(n) = O(1)

    最坏情况（最坏时间复杂度）：元素 n 在最后一个位置，T(n) = O(n)

    平均情况（平均时间复杂度）：假设元素 n 在任意一个位置的概率相同为 1/n，则循环次数 x = (1+2+3+...+n)×1/n = (1+n)/2，T(n) = O(x) = O(n)

• 空间复杂度

  • 无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，则算法空间复杂度为：S(n) = O(1)。注：S 表示 Space

    • 我们称这种算法可以 原地工作——算法所需内存空间为常量

  • 如果算法所需的内存空间与问题规模有关，则我们使用大 O 表示法去描述：

    void test(int n) {
        int flag[n];    // 申明一个长度为 n 的数组
        int i;
        // ... 此处省略很多代码
    }

    • 假设一个 int 变量占 4B，则所需内存空间 = 4(参数 n) + 4n(数组 flag) + 4(局部变量 i) = 4n + 8

    • S(n) = O(n)

    ---

    void test(int n) {
        int flag[n][n]; // 声明 n*n 的二维数组
        int i;
        // ... 此处省略很多代码
    }

    • S(n) = O(n²)

    ---

    void test(int n) {
        int flag[n][n]; // 声明 n*n 的二维数组
        int other[n];   // 声明一个长度为 n 的数组
        int i;
        // ... 此处省略很多代码
    }

    • S(n) = O(n²) + O(n) + O(1) = O(n²)

    ---

    // 算法 5——递归型
    void loveYou(int n) {
        int a,b,c;  // 声明一系列局部变量
        // ... 省略代码
        if(n > 1) {
            loveYou(n-1);
        }
        printf("I Love You %d\n", n);
    }
    
    int main() {
        loveYou(5);
    }

    • S(n) = O(n). （空间复杂度 = 递归调用的深度）

    ---

    // 算法 5 修改版
    void loveYou(int n) {
        int flag[n];    // 声明一个数组
        // ... 省略数组初始化代码
        if(n > 1) {
            loveYou(n-1);
        }
        printf("I Love You %d\n", n);
    }
    
    int main() {
        loveYou(5);
    }

    • 消耗内存空间：1+2+3+...+n = [n(1+n)/2] = (1/2)n²+(1/2)n

    • S(n) = O(n²)

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --