1.2 算法和算法评价

数据结构是存储和组织数据的方式，而算法是操作数据、解决问题的方法。如果说数据结构是"食材"，算法就是"菜谱"。二者相辅相成——好的数据结构让算法更高效，好的算法能充分发挥数据结构的优势。

算法的基本概念

什么是算法

算法（Algorithm） 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

一个简单的例子——计算 1 到 n 的和：

// 算法一：循环累加
int sum(int n)
{
    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        result += i;
    }
    return result;
}

// 算法二：高斯公式
int sum(int n)
{
    return n * (n + 1) / 2;
}

两个算法都能解决问题，但效率截然不同。算法一需要执行 n 次加法，算法二只需一次乘法和一次除法。这就是为什么要学习"算法评价"。

算法的五大特性

一个算法必须具备以下五个重要特性：

"好"算法的标准

除了五个基本特性，一个好的算法还应该满足：

• 正确性：算法能正确地解决目标问题。
• 可读性：算法易于理解，便于维护和调试。
• 健壮性：对非法输入能做出恰当的反应，而不是崩溃。
• 高效率与低存储：运行时间短、占用内存少——这正是下一节要讨论的核心。

算法效率的度量

评价一个算法的好坏，主要看两个方面：

1. 时间复杂度——算法运行需要多长时间？
2. 空间复杂度——算法运行需要多少内存？

时间复杂度

问题规模

问题规模是输入量的大小，通常用 n 表示。比如：

• 在一个数组中查找元素 → n 是数组的长度。
• 对一个列表排序 → n 是列表的元素个数。
• 计算矩阵乘法 → n 是矩阵的阶数。

频度与渐进时间复杂度

语句频度是一条语句在算法中被重复执行的次数。

int sum(int n)
{
    int result = 0;            // 执行 1 次
    for (int i = 1; i <= n; i++)
    {
        result += i;           // 执行 n 次
    }
    return result;             // 执行 1 次
}
// 总执行次数：T(n) = 1 + n + 1 = n + 2

但对于大 n 来说，常数项的影响微乎其微。我们真正关心的是当 n 趋于无穷大时，T(n) 增长的趋势。这就引出了渐进时间复杂度，通常用 大 O 记号表示。

大 O 记号

大 O 记号（Big-O Notation）描述的是算法的上界，即最坏情况下的增长率。

若存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有 T(n) ≤ c·f(n)，
则记作 T(n) = O(f(n))

通俗地说：O(f(n)) 表示算法的运行时间最多与 f(n) 成正比。

推导大 O 阶的方法：

1. 用常数 1 取代运行时间中的所有加法常数。
2. 只保留最高阶项。
3. 如果最高阶项存在且系数不为 1，则去除系数。

T(n) = 3n² + 2n + 5

→ 去掉常数项 5：3n² + 2n
→ 去掉低阶项 2n：3n²
→ 去掉系数 3：n²

∴ 时间复杂度为 O(n²)

常见时间复杂度

增长趋势对比（n = 100 时）：

O(1)      → 1 次
O(log n)  → 约 7 次
O(n)      → 100 次
O(n log n)→ 约 700 次
O(n²)     → 10,000 次
O(n³)     → 1,000,000 次
O(2ⁿ)     → 天文数字
O(n!)     → 远超宇宙原子数

时间复杂度计算示例

示例一：O(1) 常数阶

void constant(int n)
{
    int x = n * 2;      // 1 次
    int y = x + 100;    // 1 次
    cout << y << endl;  // 1 次
}
// T(n) = 3 → O(1)

算法中没有任何循环或递归，执行次数与问题规模 n 无关，就是 O(1)。

示例二：O(n) 线性阶

void linear(int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << i << endl;  // 执行 n 次
    }
}
// T(n) = n → O(n)

示例三：O(n²) 平方阶

void quadratic(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << i * j << endl;  // 执行 n×n 次
        }
    }
}
// T(n) = n² → O(n²)

示例四：O(log n) 对数阶

void logarithmic(int n)
{
    int i = 1;
    while (i < n)
    {
        i = i * 2;   // i 每次翻倍：1, 2, 4, 8, ..., n
    }
}
// 循环次数 x 满足 2^x ≥ n → x = log₂n → O(log n)

示例五：多层循环的综合分析

void mixed(int n)
{
    // 第一段：O(n²)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cout << "A";

    // 第二段：O(n)
    for (int i = 0; i < n; i++)
        cout << "B";
}
// 总时间：O(n² + n) = O(n²)，取最高阶

空间复杂度

空间复杂度 S(n) 定义为算法所耗费的存储空间，它也是问题规模 n 的函数，同样用大 O 记号表示。

一个算法运行期间所占用的存储空间包括：

1. 算法本身所占空间：存储算法的指令（这部分是固定的，通常不计入空间复杂度）。
2. 输入数据所占空间：存储输入数据。
3. 辅助变量所占空间：算法运行过程中临时占用的额外空间。

我们通常关注的是第 3 项——辅助空间。

示例

O(1) 常数空间：

int sum(int arr[], int n)
{
    int result = 0;       // 只用了 result 这一个额外变量
    for (int i = 0; i < n; i++)
    {
        result += arr[i];
    }
    return result;
}
// 无论 n 多大，只用了常数个辅助变量 → O(1)

O(n) 线性空间：

int* copyArray(int arr[], int n)
{
    int* newArr = new int[n];  // 分配了大小为 n 的新数组
    for (int i = 0; i < n; i++)
    {
        newArr[i] = arr[i];
    }
    return newArr;
}
// 辅助空间随 n 线性增长 → O(n)

O(n) 递归空间：

int factorial(int n)
{
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
// 递归深度为 n，每层递归需要栈空间 → O(n)

时间 vs 空间

时间复杂度和空间复杂度往往是矛盾的：

用空间换时间        → 缓存、哈希表、预计算
用时间换空间        → 原地算法、流式处理
时间和空间都最优    → 理想情况，常见于简单问题

在实际开发中，绝大多数情况下时间复杂度比空间复杂度更受关注——内存越来越便宜，而用户对响应时间的要求越来越高。但这不意味着可以无节制地使用内存，嵌入式等内存受限场景仍然需要严格控制空间。

完整示例

下面用一个综合案例，对比不同算法的复杂度：

#include <iostream>
using namespace std;

// O(n²)：暴力查找重复元素
bool hasDuplicate1(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] == arr[j])
                return true;
    return false;
}
// 时间复杂度 O(n²)，空间复杂度 O(1)

// O(n log n)：排序后比较相邻元素
// （这里只示意思路，排序需要额外章节学习）
//
// 1. 先排序 → O(n log n)
// 2. 遍历比较相邻元素 → O(n)
// 总时间复杂度 = O(n log n)，空间复杂度取决于排序算法

// O(n)：用哈希表记录出现过的元素（需要额外空间）
// （哈希表在后续章节详述）
//
// 遍历数组，每个元素查哈希表 → O(n)
// 时间复杂度 O(n)，空间复杂度 O(n)

小结

算法效率的评价是贯穿全书的线索。后续每学习一种数据结构和算法，我们都会分析它的时间和空间复杂度，以此来衡量它的优劣。