第1讲：算法复杂度 —— 衡量代码性能的“效率标尺”

从“能运行”到“高效运行”，掌握编程中的核心能力！
运用数学思维，精准分析程序在时间和空间上的消耗！

目录

• 数据结构与算法：程序的“骨架”与“灵魂”
• 为何需要复杂度？—— 以“旋转数组”为例
• 时间复杂度：评估执行速度的关键指标
• 空间复杂度：衡量内存占用的标准
• 常见复杂度对比：谁才是真正的高性能方案？

正文开始

你是否曾遇到以下情况：

• 代码可以正常运行，但一旦处理大规模数据就变得极其缓慢？
• 本地测试通过，提交至LeetCode却提示“超时”？
• 面对多个可行解法，难以判断哪个更优？

此时，算法复杂度将成为你的关键工具。

它帮助你穿透表象，看清代码背后的真实性能表现。

数据结构与算法：程序的“骨架”与“灵魂”

什么是数据结构？
数据结构（Data Structure）指的是计算机中组织和存储数据的方式，是数据元素之间特定关系的集合。

类比于“书架”：

• 书籍本身代表“数据”
• 书架的排列方式（如按类别、按字母顺序）则对应“数据结构”

常见的数据结构包括：数组、链表、栈、队列、树、图、哈希表等。

nums

什么是算法？
算法（Algorithm）是一组定义明确的计算步骤，用于将输入转换为期望的输出。

就像一份“菜谱”：

• 食材是“输入”
• 烹饪步骤是“算法”
• 最终做好的菜肴就是“输出”

同一个问题可能有多种算法解决。而复杂度，正是我们用来比较这些算法优劣的核心标准。

k

为什么需要复杂度？—— 从“旋转数组”谈起

一个典型例子：LeetCode 第189题“轮转数组”

给定一个数组，要求将其向右轮转 k 个位置。

思路一：暴力移动法（看似简单，实则低效）

void rotate(int* nums, int numsSize, int k) {
    while(k--) {
        int end = nums[numsSize-1];
        for(int i = numsSize - 1; i > 0; i--) {
            nums[i] = nums[i-1]; // 每次前移一位
        }
        nums[0] = end;
    }
}

这种方法在小规模数据下表现尚可，但在实际提交时容易出现超时错误。

原因在于其执行效率极低，随着数据量增长，耗时急剧上升。

时间复杂度：衡量“运行快慢”的关键指标

为什么不直接测量程序的运行时间？

• 环境依赖性强：不同设备、编译器会导致结果差异；
• 无法提前预估：必须写完代码才能测试，不利于设计阶段优化；
• 受数据规模影响大：输入越大，时间波动越剧烈。

核心思想：
使用“基本操作的执行次数”来代替“实际运行时间”。
因为执行次数与运行时间成正比，且不受硬件或系统影响。

大O渐进表示法 —— 复杂度分析的“黄金标准”

大O符号（Big O）是一种描述函数在输入规模趋于无穷时增长趋势的数学工具。
它关注的是算法随数据量增大的最坏情况下的增长速率。

推导大O的三个步骤口诀

T(N) = N? + 2N + 10

T(N) = 3N?

T(N) = 100

O(N?)

O(N?)

O(1)

时间复杂度计算实例

实例1：双重循环结构

void Func1(int N) {
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ++count; // 执行 N×N 次
        }
    }
    // 其他 O(N) 和 O(1) 操作
}

主导项为 N，因此时间复杂度为 O(N)。

O(N?)

T(N) = N? + 2N + 10

O(N?)

实例2：线性循环，含常数倍数

void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N; ++k) {
        ++count; // 执行约 2N 次
    }
    // 后续 O(1) 操作
}

尽管循环上限是 2N，但常数系数被忽略，复杂度仍为 O(N)。

O(N)

T(N) = 2N + 10

O(N)

实例3：固定次数循环

void Func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; ++k) {
        ++count; // 固定执行100次，与N无关
    }
}

无论N如何变化，执行次数恒定，故时间复杂度为 O(1)。

O(1)

T(N) = 100

O(1)

实例4：基于二分思想的增长模式

void func5(int n) {
    int cnt = 1;
    while (cnt < n) {
        cnt *= 2; // 每次翻倍，循环次数约为 log(n)
    }
}

设执行 x 次，则有 2^x ≥ n → x ≈ logn
因此时间复杂度为 O(log n)。

O(log N)

x

2^x = n

x = log?n

O(log N)

注意点：

在大O表示法中，logn、logn、ln n 等所有对数形式均视为等价，底数不影响复杂度级别。

log?N

log N

lg N

空间复杂度：衡量“内存开销”的标尺

空间复杂度关注的是算法在运行过程中临时占用的存储空间大小，通常也用大O表示法描述。

它不包含原始输入所占空间，仅统计额外使用的辅助空间。

例如：

• 仅使用几个变量 → O(1)
• 创建长度为N的新数组 → O(N)
• 递归深度达到N层 → O(N)（考虑调用栈）

常见复杂度对比：谁是真正的“性能王者”？

以下是常见时间复杂度按效率从高到低的排序：

1. O(1) —— 常数时间，最优
2. O(log n) —— 对数时间，高效适用于大数据
3. O(n) —— 线性时间，可接受
4. O(n log n) —— 常见于高效排序算法
5. O(n) —— 平方时间，中小数据可用
6. O(2), O(n!) —— 指数级，仅适合极小规模

选择合适算法的本质，就是在时间与空间之间做出合理权衡。

递归调用示例 —— 阶乘实现

O(N)

long long Fac(size_t N) {
    if(N == 0) return 1;
    return Fac(N-1) * N; // 递归调用N次
}

N

O(N)

算法执行情况分析：最好、最坏与平均情形

strchr

O(1)

O(N)

O(N)

行业惯例：通常所说的“时间复杂度”指的是最坏情况下的复杂度，因为它为算法性能提供了可靠的上界保障。

冒泡排序的时间复杂度分析 —— 最坏情形

O(N?)

void BubbleSort(int* a, int n) {
    for (size_t end = n; end > 0; --end) {
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) Swap(&a[i-1], &a[i]);
        }
    }
}

T(N) = N*(N-1)/2

O(N?)

空间复杂度详解

空间复杂度是衡量算法在执行过程中临时额外占用存储空间大小的指标。

• 不包括程序整体内存使用量
• 不包含原始输入数据所占空间
• 重点关注的是算法中额外申请的变量或数据结构

其计算方法与时间复杂度类似，采用大O渐进表示法进行估算。

空间复杂度实例解析

实例一：冒泡排序的空间消耗

O(1)

void BubbleSort(int* a, int n) {
    // ...
    int exchange = 0; // 仅使用常数个辅助变量
}

N

O(1)

实例二：递归阶乘的空间开销

O(N)

long long Fac(size_t N) {
    if(N == 0) return 1;
    return Fac(N-1) * N;
}

N

N

O(N)

实例三：使用辅助数组的旋转操作

O(N)

void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize]; // 动态申请长度为N的新数组
    // ...
}

N

O(N)

常见时间复杂度对比：谁才是性能之王？

O(1)

O(log N)

O(N)

O(N log N)

O(N?)

O(2^N)

• 理想目标：尽可能设计出

  O(N)

  或更优的

  O(log N)

  复杂度算法
• 性能警示：应避免在处理大规模数据时使用

  O(N?)

  及以上级别的算法

旋转数组问题的三种策略复杂度对比

O(k * N)

O(N?)

O(1)

O(N)

O(N)

O(N)

O(1)

最优方案实现：三次反转算法

void reverse(int* nums, int begin, int end) {
    while(begin < end) {
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
        begin++; end--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize; // 处理k大于数组长度的情况
    reverse(nums, 0, numsSize - k - 1); // 反转前n-k个元素
    reverse(nums, numsSize - k, numsSize - 1); // 反转后k个元素
    reverse(nums, 0, numsSize - 1); // 整体反转一次
}

O(N)

O(1)

算法复杂度“黄金法则”总结

• 法则一：时间优先 —— 优先优化时间复杂度，直接提升用户体验
• 法则二：空间换时间 —— 在资源允许时，可通过增加空间使用来加速运算（例如哈希表）
• 法则三：大O为准绳 —— 使用大O记号进行科学分析，而非主观猜测
• 法则四：以最坏情况为基准 —— 分析时重点关注最坏情形，确保系统稳定性

恭喜你！

你已经掌握了程序员的“内功心法”——

算法复杂度分析！

从此，你不再是“只会写代码的码农”，而是“能设计高效算法的工程师”！

nums

确保程序在各种输入条件下都能保持可接受的性能表现。