复杂度是计算机科学中非常核心的一个概念，用于衡量一个算法的“好坏”
为什么需要复杂度分析

1. 脱离硬件依赖：不同的机器（CPU、内存、硬盘）性能不同，同一段代码在不同机器上的运行时间会差异很大。理论分析可以消除这种硬件差异
2. 脱离数据依赖：如果测试数据规模太小，或者测试数据本身的特点（如是否已排序），可能无法真实反映算法的性能。比如，一个算法对小规模数据很快，对大规模数据极慢
3. 成本于可行性：在算法设计阶段，往往需要从多个候选方案中选优，不可能每个方案都实现并测试。复杂度分析可以在编码前就进行理论上的评估
4. 洞察本质：复杂度分析帮助我们理解算法随问题规模增长时，其资源消耗的增长趋势，这是评价算法可扩展性的关键

什么是复杂度
算法的复杂度分为两个维度：

1. 时间复杂度（Time Complexity）：不是计算程序的具体运行时间，而是计算算法执行基本操作（或称语句）的次数。它反映了运行时间随输入数据规模增大的增长趋势
2. 空间复杂度（Space Complexity）：计算算法运行过程中所需的存储空间随输入数据规模增大的增长趋势。这通常指除了输入数据本身所占空间之外，算法运行所需的额外空间

大O表示法（Big O Notation）

复杂度通常用大O表示法来描述。它表示的是算法复杂度的一个上界（Upper Bound），即最坏情况下的复杂度
定义： 如果存在正常数 $c$ 和 $n_o$ ，使得当 $ n \ge n_o$ 时，$T(n) \le c * f(n) $ ，则记为 T(n) = O(f(n)) 通俗理解： 大O表示法抓主要矛盾，忽略常数、系数和低阶项，只关注增长最快的那部分（最高阶项）。因为它对增长趋势的影响最大

示例：

• $T(n) = 3n^2 + 2n + 1$，我们记为$O(n^2)$，因为当 n 很大时，$n^2$起主导作用
• $T(n) = 5n + 10$，我们记为$O(n)$
• $T(n) = 1000$，我们记为$O(1)$，表示常数时间

特别的，对数复杂度的底数通常不影响渐进复杂度的表示
根据换底公式：$\log_ax=\frac{\log_bx}{\log_ba}$
也就是说，把对数的底数从a转换为b只会多一个常数因子$\frac{1}{\log_ba}$
在大O表示法下，常数因子是不计入复杂度的\

• 数学上：对数底数可以是任何正数且不等于1
• 算法分析上：底数通常省略，因为大O不看常数因子
• 常见约定：
  • 二分查找、分治算法 -> 二进制对数$\log_2n$
  • 信息论、熵相关 -> 自然对数$\ln n$
  • 书写算法复杂度 -> 不标底数

常见的时间复杂度

按性能从优到劣排列：

直观感受：假设每秒钟能执行 10^8 次操作，不同复杂度算法能处理的数据规模差异巨大

如何分析一段代码的复杂度

核心： 关注循环结构和递归调用

1. 顺序执行：复杂度为各部分相加，取最大值

// O(1) + O(n) + O(n²) -> O(n²)
do_something(); // O(1)

for (int i = 0; i < n; ++i) { ... } // O(n)

for (int i = 0; i < n; ++i)  // O(n²)
    for (int j = 0; j < n ; ++j) { ... }

2. 单层循环：循环次数 * 循环体内复杂度

// O(n)
for (int i = 0; i < n; ++i)
    do_something(); // 假设 do_something 是 O(1)

3. 嵌套循环：各层循环次数的乘积

// O(m * n)
for (int i = 0; i < n; ++i)
    for (int j = 0; j < m ++j)
        do_something(); // O(1)

// O(n²)
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        do_something(); // O(1)

4. 对数复杂度：通常出现在循环变量以倍数增长或衰减时

// O(log n)
int i = 1;

while(i < n)
{
    i *= 2; // 每次循环规模减半
    do_something(); // O(1)
}

5. 递归算法：分析其递归树或使用主定理（Master Theorem）。例如斐波那契数列的递归实现是$O(2^n)$，而归并排序的递归实现是O(n log n)

空间复杂度分析

与分析时间复杂度类似，关注额外开辟的数组、变量、递归调用栈等

1. O(1)

// 只用了几个固定变量
int algorithm()
{
    int a = 1;
    int b = 2;
    return a + b;
}

2. O(n)

// 开辟了一个大小为 n 的数组
std::vector<int> algorithm(int n)
{
    std::vector<int> vec;
    for (int i = 0; i < n; ++i)
        vec.push_back(i);

    return vec;
}

3. O(n²)

// 开辟一个 n * n的二维数组
std::vector<std::vector<int>> algorithm(int n)
{
    std::vector<std::vector<int>> vec(n, std::vector<int>(n));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n ++j)
            vec[i][j] = i + j;
    
    return vec;
}

4. 递归调用栈：递归深度带来的空间消耗

// 空间复杂度O(n)
// 因为最新会递归 n 层，每层调用需要常数空间，所以是O(n)

int factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * factorial(n - 1);
}

最佳、最差、平均情况

通常要关注最坏情况时间复杂度，因为它给出了算法运行时间的上界，保证了性能不会比这更差

• 最佳情况（Best Case）：算法在最理想输入下的性能（例如，数组第一个元素就是要找的目标）
• 最坏情况（Worst Case）：算法在最糟糕输入下的性能（例如，数组最后一个元素就是要找的目标，或者根本不存在）
• 平均情况（Average Case）：考虑所有可能输入，计算预期运行时间。分析起来通常最复杂

其他重要的渐近符号（Asymptotic Notations）

大O表示法（上界）是最常用的，但为了更精确地描述算法行为，计算机科学中定义了一组渐近符号

误区与难点

1. 不要忽略常数因子（但大O表示法忽略它）

• 大O表示法：1000n和n都是O(n)
• 现实世界：如果1000n的算法和2n²的算法对比，当n < 500时，反而是O(n²)的算法更快
• 结论：大O分析适用于大规模数据。对于小规模数据，常数因子可能起决定性作用。这就是为什么快速排序在小数组上回切换使用插入排序的原因

2. 递归算法的复杂度分析 这是最复杂的一部分。主要有两种方法：

• 递归树法：画出递归调用树，计算每一层的工作量和总层数，然后求和
• 主定理：一个强大的公式，可以直接求解形如T(n) = aT(n/b) + f(n)的递归方程

3. 均摊分析（Amortized Analysis） 有些操作单次看可能很耗时，但一系列操作总起来看平均代价很低

• 经典例子：动态数组的插入操作
  • 大多数情况下，在尾部插入是O(1)
  • 但当空间不足时，需要分配一块新的更大的内存，并把旧元素全部拷贝过去，这是一个O(n)的操作
  • 但不能说插入操作时O(n)，因为昂贵的扩容操作不会频繁发生
  • 通过均摊分析，可以证明连续进行 n 次插入操作的总时间是O(n)，因此单次插入的均摊代价是O(1)

4. 空间复杂度的隐藏成本

• 递归调用栈：容易被忽略。递归深度越大，所需栈空间越多，可能导致栈溢出。例如，深度为 n 的递归，空间复杂度至少是O(n)
• 函数调用开销：每次函数调用都会在栈上压入返回地址、参数等，虽然每个开销是常数，但大量调用时不可忽视

建议

1. 从里到外分析：从最内层的循环/递归开始分析，逐步向外
2. 关注最坏情况：除非特别说明，否则默认分析最坏情况复杂度
3. 理解而不是死记：记住常见算法的复杂度是好的，但更重要的是理解为什么是哪个复杂度
4. 权衡时空：时间和空间往往不可兼得，这就是所谓的“时空权衡”。有时可以用更多的空间（如查表、缓存）来换取更快的速度，反之亦然。要根据实际场景（如嵌入式设备内存紧张，服务器追求高并发低延迟）做决定
5. Big O是工具，不是目的：它的目的是帮助选择和理解算法，而不是算法的最终判决书。一个理论复杂度更优的算法可能因为常数因子过大、缓存不友好、并行度差等原因，在实际应用中反而不如一个理论复杂度稍差的算法