算法

2022/07/28

Table of Contents

算法效率评估

算法评价维度

算法的设计目标是什么？如何来评判算法的好与坏？整体上看，设计算法时追求两个层面的目标。

  1. 找到问题解法。算法需要能够在规定的输入范围下，可靠地求得问题的正确解。
  2. 寻求最优解法。同一个问题可能存在多种解法，而我们希望算法效率尽可能的高

换言之，在可以解决问题的前提下，算法效率则是主要评价维度，包括：

数据结构与算法追求“运行速度快、占用内存少”，而如何去评价算法效率则是非常重要的问题，只有知道如何评价算法，才能去做算法之间的对比分析，以及优化算法设计

效率评估方法

实际测试

假设算法A和算法B，都能够解决同一问题，现在需要对比两个算法之间的效率，最直接的方式，就是找一台计算机，把两个算法都完整跑一遍，并监控记录运行时间和内存占用情况。这种评估方式能够反映真实情况，但存在以下问题：

  1. 难以排除测试环境的干扰因素：硬件配置会影响到算法的性能表现。
  2. 展开完整测试非常耗费资源：随着输入数据量的大小变化，算法会呈现出不同的效率表现。比如，有可能输入数据量较小时，算法 A 运行时间短于算法 B ，而在输入数据量较大时，测试结果截然相反

理论估算

实际测试具有较大的局限性，我们可以通过计算来进行分析，将此估算方法称为复杂度分析 (Complexity Analysis)或渐近复杂度分析 (Asymptotic Complexity Analysis)

复杂度分析评估的是算法运行效率随着输入数据量增多时的增长趋势

复杂度分析克服了实际测试方法的弊端。一是独立于测试环境，分析结果适用于所有运行平台。二是可以体现不同数据量下的算法效率，尤其是可以反映大数据量下的算法性能

时间复杂度

统计算法运行时间

  1. 首先需要 确定运行平台 ，包括硬件配置、编程语言、系统环境等，这些都会影响到代码的运行效率。
  2. 评估 各种计算操作的所需运行时间 ，例如加法操作 + 需要 1 ns ，乘法操作 * 需要 10 ns ，打印操作需要 5 ns 等。
  3. 根据代码 统计所有计算操作的数量 ，并将所有操作的执行时间求和，即可得到运行时间

例如以下代码，输入数据大小为 (n) ，根据以上方法，可以得到算法运行时间为 (6n + 12) ns

（1+1+10+(1+5)*n）=6n+12 ns

// 在某运行平台下
func algorithm(n int) {
    a := 2      // 1 ns
    a = a + 1   // 1 ns
    a = a * 2   // 10 ns
    // 循环 n 次
    for i := 0; i < n; i++ {    // 1 ns
        fmt.Println(a)          // 5 ns
    }
}

但实际上， 统计算法的运行时间既不合理也不现实。首先，我们不希望预估时间和运行平台绑定，毕竟算法需要跑在各式各样的平台之上。其次，我们很难获知每一种操作的运行时间，这为预估过程带来了极大的难度

统计时间增长趋势

「时间复杂度分析」采取了不同的做法，其统计的不是算法运行时间，而是 算法运行时间随着数据量变大时的增长趋势

设输入数据大小为 n ，给定三个算法 A , B , C 。

// 算法 A 时间复杂度：常数阶
func algorithm_A(n int) {
    fmt.Println(0)
}
// 算法 B 时间复杂度：线性阶
func algorithm_B(n int) {
    for i := 0; i < n; i++ {
        fmt.Println(0)
    }
}
// 算法 C 时间复杂度：常数阶
func algorithm_C(n int) {
    for i := 0; i < 10000; i++ {
        fmt.Println(0)
    }
}

image-20230226142257824

相比于直接统计运行时间，时间复杂度分析的做法好处与不足如下：

时间复杂度可以有效评估算法效率在 (n > 1) 时慢于算法 A ，在 (n > 1000000) 时慢于算法 C 。实质上，只要输入数据大小 (n) 足够大，复杂度为「常数阶」的算法一定优于「线性阶」的算法，这也正是时间增长趋势的含义

时间复杂度的推算方法更加简便。在时间复杂度分析中，我们可以将统计「计算操作的运行时间」简化为统计「计算操作的数量」，这是因为，无论是运行平台还是计算操作类型，都与算法运行时间的增长趋势无关。因而，我们可以简单地将所有计算操作的执行时间统一看作是相同的“单位时间”，这样的简化做法大大降低了估算难度。

时间复杂度也存在一定的局限性。比如，虽然算法 A 和 C 的时间复杂度相同，但是实际的运行时间有非常大的差别。再比如，虽然算法 B 比 C 的时间复杂度要更高，但在输入数据大小 (n) 比较小时，算法 B 是要明显优于算法 C 的。对于以上情况，我们很难仅凭时间复杂度来判定算法效率高低。然而，即使存在这些问题，计算复杂度仍然是评判算法效率的最有效且常用的方法

常见类型

设输入数据大小为 (n) ，常见的时间复杂度类型有（从低到高排列）

O(1) < O(log n) < O(n) < O(n^2) < O(2^n)

image-20230226143032563

常数阶 O(1)

常数阶的操作数量与输入数据大小 (n) 无关，即不随着 (n) 的变化而变化。

对于以下算法，无论操作数量 size 有多大，只要与数据大小 (n) 无关，时间复杂度就仍为 O(1) 。

/* 常数阶 */
func constant(n int) int {
    count := 0
    size := 100000
    for i := 0; i < size; i++ {
        count++
    }
    return count
}

线性阶 O(n)

线性阶的操作数量相对输入数据大小成线性级别增长。线性阶常出现于单层循环。

/* 线性阶 */
func linear(n int) int {
    count := 0
    for i := 0; i < n; i++ {
        count++
    }
    return count
}

「遍历数组」和「遍历链表」等操作，时间复杂度都为 O(n) ，其中 (n) 为数组或链表的长度。

平方阶 O(n^2)

平方阶的操作数量相对输入数据大小成平方级别增长。平方阶常出现于嵌套循环，外层循环和内层循环都为 O(n) ，总体为 O(n^2)

/* 平方阶 */
func quadratic(n int) int {
    count := 0
    // 循环次数与数组长度成平方关系
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            count++
        }
    }
    return count
}

image-20230226143405972

指数阶 O(2^n)

生物学科中的“细胞分裂”即是指数阶增长：初始状态为 (1) 个细胞，分裂一轮后为 (2) 个，分裂两轮后为 (4) 个，……，分裂 (n) 轮后有 (2^n) 个细胞。

/* 指数阶（循环实现）*/
func exponential(n int) int {
    count, base := 0, 1
    // cell 每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for i := 0; i < n; i++ {
        for j := 0; j < base; j++ {
            count++
        }
        base *= 2
    }
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count
}

image-20230226145318985

在实际算法中，指数阶常出现于递归函数。例如以下代码，不断地一分为二，分裂 (n) 次后停止。

/* 指数阶（递归实现）*/
func expRecur(n int) int {
    if n == 1 {
        return 1
    }
    return expRecur(n-1) + expRecur(n-1) + 1
}

对数阶 O(log n)

对数阶与指数阶正好相反，后者反映“每轮增加到两倍的情况”，而前者反映“每轮缩减到一半的情况”。对数阶仅次于常数阶，时间增长得很慢，是理想的时间复杂度

对数阶常出现于「二分查找」和「分治算法」中，体现“一分为多”、“化繁为简”的算法思想。

/* 对数阶（循环实现）*/
func logarithmic(n float64) int {
    count := 0
    for n > 1 {
        n = n / 2
        count++
    }
    return count
}

image-20230226145611765

与指数阶类似，对数阶也常出现于递归函数。以下代码形成了一个高度为 (log_2 n) 的递归树

/* 对数阶（递归实现）*/
func logRecur(n float64) int {
    if n <= 1 {
        return 0
    }
    return logRecur(n/2) + 1
}

空间复杂度

「空间复杂度 Space Complexity」统计 算法使用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度很类似。

算法相关空间

算法运行中，使用的内存空间主要有以下几种：

暂存空间可分为三个部分：

image-20230226145944984

/* 结构体 */
type node struct {
    val  int
    next *node
}

/* 创建 node 结构体  */
func newNode(val int) *node {
    return &node{val: val}
}

/* 函数 */
func function() int {
    // do something...
    return 0
}

func algorithm(n int) int { // 输入数据
    const a = 0             // 暂存数据（常量）
    b := 0                  // 暂存数据（变量）
    newNode(0)              // 暂存数据（对象）
    c := function()         // 栈帧空间（调用函数）
    return a + b + c        // 输出数据
}

推算方法

空间复杂度的推算方法和时间复杂度总体类似，只是从统计“计算操作数量”变为统计“使用空间大小”。与时间复杂度不同的是，我们一般只关注「最差空间复杂度」。这是因为内存空间是一个硬性要求，我们必须保证在所有输入数据下都有足够的内存空间预留。

最差空间复杂度中的“最差”有两层含义，分别为输入数据的最差分布、算法运行中的最差时间点。