01 · 算法基础与复杂度（Algorithm Basics & Complexity）

📅 预计 90 分钟　|　⭐ 本章主题：用同一把尺子衡量算法"快不快、省不省"
📌 中英术语见文末

1.1 什么是算法

算法 = 一份精确的菜谱

想象你要做一道番茄炒蛋，把步骤写在纸上：打蛋、切番茄、热油、下锅、调味、装盘。算法（algorithm）就是这份菜谱——把"解决一个问题的步骤"用计算机能执行的方式精确写出来。一份合格的算法有五个特性：

  • 有穷性（finiteness）：步骤必须有限，任何输入下都不能无限执行。
  • 确定性（definiteness）：每一步的含义唯一。"放适量盐"这种含糊说法在算法里不合格。
  • 可行性（effectiveness）：每一步都能真正执行，不依赖某种魔法。
  • 有输入（input）：允许 0 个或多个输入。
  • 有输出（output）：至少一个输出，否则算完没人知道结果。

算法和程序不是一回事：算法是思想，可以用自然语言、伪代码、流程图描述，与编程语言无关；程序是算法用某一种语言写出来、能实际运行的载体。同一个算法换 Python、C、Java 各写一遍，算法本身没有变。

# 求数组最大值：挨个看，随时记住见过最大的
def find_max(nums):
    best = nums[0]
    for x in nums[1:]:
        if x > best:
            best = x
    return best

print(find_max([3, 7, 2, 9, 4]))
# 输出: 9

⚠️ 常见错误

  1. 把"程序"和"算法"划等号：程序是算法的实现，换语言、改写法都不改变算法本身。
  2. 忽略有穷性：某些输入下永远循环不结束的"算法"其实是 bug，不是算法。
  3. 用"跑得最快"作为唯一标准：算法评估还涉及占用内存多少、代码是否好维护等，本章先讲最重要的时间与空间。

1.2 为什么要关心复杂度

同一个问题，两种解法能差多远？

同样是"在 100 万元素里找一个数"：一种解法要检查 1 次，另一种要检查 100 万次；同样是排序，快的算法毫秒级完成，慢的算法能排到天荒地老。复杂度（complexity）就是用来量化这种差别的标准，它回答两个问题：

  1. 时间上要跑多久——时间复杂度（time complexity）
  2. 空间上占多少内存——空间复杂度（space complexity）

关键在"增长趋势"而不是"具体秒数"：同样的代码，换了更快的电脑就快一点，但"数据量翻一倍时程序慢多少"这件事，是算法本身决定的，跟电脑快慢无关。所以我们关注的是输入规模 n 增大时，运行时间按什么规律增长。

# 规模增大时，差距如何放大？
import time

for n in [1_000, 10_000, 100_000]:
    t0 = time.perf_counter()
    s = sum(i * i for i in range(n))      # 单循环，O(n)
    t1 = time.perf_counter()
    # 双重循环，O(n²)，注释掉避免真的跑很久
    # for i in range(n):
    #     for j in range(n):
    #         s += i + j
    print(f"n={n}: 单循环耗时 {t1 - t0:.6f} 秒")
# 输出形如: n=1000: 单循环耗时 0.0002 秒 ...

⚠️ 常见错误

  1. 拿"实测秒数"直接说复杂度：不同机器、不同输入量秒数都会变，复杂度描述的是增长规律而非固定秒数。
  2. 忽视输入规模：n 很小时所有算法看起来都快，复杂度只有在 n 足够大时才真正区分优劣。

1.3 大 O 记号 ⭐

把运行时间"四舍五入"成量级

大 O 记号（Big-O notation）是所有复杂度分析的语言。它的核心思想是：只关心"增长趋势"，忽略常数系数和低阶项。

举个例子：某算法实际执行 3n² + 5n + 7 次基本操作。当 n 很大时：

  • 3n² 是主角，5n + 7 微不足道；
  • 系数 3 只是放大倍数，不影响增长规律。

所以我们就说这个算法的时间复杂度是 O(n²)，读作"大 O 的 n 平方"。

💡 记忆口诀：大 O 是"四舍五入"——常数不管、低阶扔掉、只看最大那一项。它回答的问题是"n 翻倍时，时间怎么变"，而不是"具体几毫秒"。

常见量级从慢到快排列（n 是输入规模）：

记号 读法 增长感觉 n 翻倍时时间
O(1) 常数 一动不动 不变
O(log n) 对数 涨得极慢 只加一点点
O(n) 线性 匀速 翻倍
O(n log n) 线性对数 比线性略快 略多于翻倍
O(n²) 平方 急剧 变成 4 倍
O(2ⁿ) 指数 爆炸 变成平方倍 
# 三个典型量级的直观对比
import math

def o_1(n):   return 1
def o_log(n): return math.log2(n)
def o_n(n):   return n
def o_n2(n):  return n * n

for n in [10, 100, 1000]:
    print(f"n={n:>5}: O(1)={o_1(n):>5}  O(log n)={o_log(n):>7.1f}  "
          f"O(n)={o_n(n):>5}  O(n²)={o_n2(n):>8}")
# 输出:
# n=   10: O(1)=    1  O(log n)=    3.3  O(n)=   10  O(n²)=     100
# n=  100: O(1)=    1  O(log n)=    6.6  O(n)=  100  O(n²)=   10000
# n= 1000: O(1)=    1  O(log n)=   10.0  O(n)= 1000  O(n²)= 1000000

⚠️ 常见错误

  1. 把 O(n) 当成"执行 n 次"：O(n) 描述的是随 n 线性增长的量级，具体执行次数可能是 2n、3n，只要是常数倍，都记 O(n)。
  2. 保留低阶项：O(n² + n) 应写作 O(n²)，O(2n + 10) 应写作 O(n)。
  3. 混淆 log 底数：log₂n、log₁₀n 只差常数倍，在大 O 记号里都写作 O(log n)，不需要写底数。

1.4 时间复杂度分析 ⭐

分析套路：数循环、看嵌套

绝大多数算法的耗时集中在循环和递归上（递归在第 02 章讲）。分析的基本套路：

  1. 找到随 n 变化的基本操作（如比较、加法）；
  2. 数它大概执行多少次；
  3. 用大 O 概括。

单个循环：执行 n 次，O(n)。

嵌套循环：外层 n 次，内层 n 次，相乘得 O(n²)。

每次砍半：n、n/2、n/4……一共约 log₂n 次，O(log n)。

def count_ops(n):
    """统计示例：一重循环 + 一重嵌套循环"""
    s = 0
    for i in range(n):              # 外层 n 次
        s += i                      # O(n) 部分
    for i in range(n):              # 外层 n 次
        for j in range(n):          # 内层 n 次
            s += i * j              # O(n²) 部分
    return s
# 总复杂度: O(n) + O(n²) = O(n²)，取最大项

# O(log n) 的典型：每轮把规模减半
def halve_count(n):
    cnt = 0
    while n > 1:
        n //= 2
        cnt += 1
    return cnt

print(halve_count(1024))   # 1024 减半几次到 1？→ 10 次
# 输出: 10

⚠️ 常见错误

  1. 嵌套循环一定相乘？不一定：内层循环次数是固定的（如 range(100)），则内外不再相乘，整体是 O(n) 而不是 O(n²)。
  2. 两个独立循环错误相乘：先后两个单循环是 O(n) + O(n) = O(n)，不是 O(n²)；只有嵌套才相乘。
  3. 忽略了循环里的 O(log n) 步骤：内层用二分法之类，内层成本是 O(log n)，整体是 O(n log n) 而非 O(n)。

1.5 空间复杂度

除了时间，还要看"占多大地方"

空间复杂度（space complexity）衡量算法运行过程中额外消耗的内存大小，同样用大 O 表示。分析时只统计额外辅助空间——输入本身占的空间通常不算。

def sum_square(n):
    """只用一个累加变量，额外空间 O(1)"""
    total = 0
    for i in range(n):
        total += i * i
    return total
# 空间复杂度: O(1)，无论 n 多大，辅助空间恒定

def make_list(n):
    """新建了一个长度为 n 的列表，额外空间 O(n)"""
    return [i * 2 for i in range(n)]
# 空间复杂度: O(n)，列表随 n 线性增长

典型规律：

  • 只用了几个变量 → O(1)；
  • 新建了长度为 n 的数组/列表 → O(n)；
  • 新建了 n×n 的二维表 → O(n²)（第 05 章动态规划常见）；
  • 递归深度为 n 时栈空间 O(n)（见第 02 章）。

时间与空间往往需要权衡：用"空间换时间"是常见策略，比如提前建好哈希表让查询变 O(1)，但付出了 O(n) 的存储。

⚠️ 常见错误

  1. 把输入数组的空间也算进去：空间复杂度默认只算算法自己额外申请的辅助空间。
  2. 只盯时间不看空间：有的算法时间极快但内存爆炸（比如建 n² 的表），真实环境同样不可用。
  3. 忘记递归栈空间：递归每层调用都占栈内存，深度 n 的递归空间是 O(n)，不是 O(1)。

1.6 常见复杂度对比表 ⭐

同一规模下，量级差距有多夸张

把六个典型量级放在同一张表里，感受 n 增大时"差几个数量级"：

记号 名称 n=10 n=100 n=1,000 n=1,000,000 典型例子
O(1) 常数 1 1 1 1 数组按下标取值、哈希表查询
O(log n) 对数 ≈3 ≈7 ≈10 ≈20 二分查找、平衡树查找
O(n) 线性 10 100 1,000 1,000,000 顺序查找、求和
O(n log n) 线性对数 ≈33 ≈664 ≈9,966 ≈2×10⁷ 归并排序、快速排序、堆排序
O(n²) 平方 100 10,000 1,000,000 10¹² 冒泡、选择、插入排序
O(2ⁿ) 指数 1,024 ≈10³⁰ 无法完成 无法完成 朴素斐波那契、子集枚举

观察要点：

  1. O(n log n) 是"优雅"的量级：能处理百万级甚至更大数据，是排序等问题的实用上限；
  2. O(n²) 只能对付中等规模：n=1 万时就是 1 亿次操作，再大就吃力；
  3. O(2ⁿ) 是指数墙：n 到 30 左右就基本不可行，n=100 就是天文数字——遇到这种复杂度要想办法优化。

💡 记忆口诀："常对线，对平方，指爆头"——O(1) 常数、O(log n) 对数、O(n) 线性、O(n log n)、O(n²) 平方、O(2ⁿ) 指数，最后一个"爆头"是指数爆炸。

⚠️ 常见错误

  1. 拿"实际能跑完"判断复杂度是否可接受：数据规模小的时候 O(n²) 也能秒过，但规模一大立刻现形，务必看增长趋势。
  2. 误记排序复杂度：比较类排序的最优下界是 O(n log n)，记住 O(n²) 的是冒泡/选择/插入这类基础排序。
  3. 把指数复杂度当"慢一点"：O(2ⁿ) 不是慢一点，是 n 稍大就永远算不完。

1.7 最好 / 最坏 / 平均情况

同一算法，不同输入表现不同

同一个算法，最"幸运"和最"倒霉"的输入，耗时可以差很远。以顺序查找（linear search）为例：

  • 最好情况：第一个元素就是目标，1 次找到，O(1)；
  • 最坏情况：目标在末尾或不存在，遍历全部，O(n)；
  • 平均情况：假设目标随机分布，平均比较 n/2 次，仍是 O(n)。

三个概念要分清：

  • 最好情况复杂度（best case）：最优输入下的复杂度，通常意义不大，因为"最优输入"很难保证。
  • 最坏情况复杂度（worst case）：最差输入下的复杂度，是保证值——不会比它更糟，工程上最关心它。
  • 平均情况复杂度（average case）：对所有可能输入取平均，需要假设输入分布，分析更复杂。
def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

nums = [5, 3, 8, 1, 9]
print(linear_search(nums, 5))   # 最好情况：第一个就命中 → O(1)
# 输出: 0
print(linear_search(nums, 7))   # 最坏情况：不存在，扫完全部 → O(n)
# 输出: -1

严谨起见，大 O 记号更准确地描述的是上界。配套的三个希腊字母记号中：

  • Ω（Omega）：下界，表示"至少这么快"；
  • Θ（Theta）：同时是上界和下界，表示"就是这个量级"；
  • O（Big-O）：上界，表示"最多这么慢"，最常用。

日常分析和考试中，通常默认讨论最坏情况的时间复杂度。

⚠️ 常见错误

  1. 只报最好情况：面试和教材默认问最坏情况，报"最好情况 O(1)"会误导。
  2. 把平均当最坏：有些算法平均和最好表现好，但最坏会退化（如快速排序对已有序数据退化到 O(n²)，见第 03 章），必须两条都清楚。
  3. 混淆 Ω 和 O：O 是上界（顶多这么慢），Ω 是下界（至少这么快），方向不要反。

1.8 Python 里如何测量耗时

用 time / timeit 量化直觉

分析理论复杂度之外，实际验证时用标准库测量。time.perf_counter() 提供高精度计时；timeit 模块更适合重复测量求稳定值。

import time
import timeit

# 方法一：手工计时
t0 = time.perf_counter()
sum(range(1_000_000))
t1 = time.perf_counter()
print(f"手工计时: {t1 - t0:.6f} 秒")

# 方法二：timeit 重复执行取最小值（更稳定）
t = timeit.timeit("sum(range(1_000_000))", number=10)
print(f"timeit 平均: {t / 10:.6f} 秒")

# 输出形如:
# 手工计时: 0.023000 秒
# timeit 平均: 0.022500 秒

注意：实测只能帮你验证"是不是同一个量级"，不能代替理论分析。真正的判断标准永远是复杂度——因为测试数据再大也有上限，而理论刻画的是所有规模的规律。

⚠️ 常见错误

  1. 用一次测量就下结论：机器负载、后台进程都会干扰，重复测量取最小值更可信。
  2. 测过就算数，不写复杂度推导：实测只验证，推导才能解释"为什么是这个量级"。
  3. 把小规模数据的时间差当真：n 小时刻所有算法都接近 0 秒，看不出差别，要让 n 足够大。

🧠 记忆口诀

  • 算法五性：有穷、确定、可行、有输入、有输出——"有穷确定可执行，输入输出不能少"。
  • 大 O 四舍五入：常数不管、低阶扔掉、只看最大项，问的是"n 翻倍时怎么变"。
  • 复杂度阶梯：常对线、对平方、指爆头——O(1)→O(log n)→O(n)→O(n log n)→O(n²)→O(2ⁿ)。
  • 分析套路：找基本操作 → 数执行次数 → 嵌套相乘、独立相加 → 大 O 概括。
  • 空间换时间：多开点数组/表把查询变 O(1)，是常见优化思路。

📌 中英术语表（本讲）

中文 English 说明
算法 algorithm 解决问题的精确定义步骤
程序 program 算法用某种语言的具体实现
复杂度 complexity 衡量资源消耗的量级
时间复杂度 time complexity 运行时间随规模的增长规律
空间复杂度 space complexity 额外内存随规模的增长规律
大 O 记号 Big-O notation 描述增长上界，O(f(n))
上界 / 下界 upper bound / lower bound O 记上界、Ω 记下界
常数 / 对数 constant / logarithmic O(1) / O(log n)
线性 / 平方 / 指数 linear / quadratic / exponential O(n) / O(n²) / O(2ⁿ)
基本操作 basic operation 复杂度计数的最小单位
最好情况 best case 最有利输入下的复杂度
最坏情况 worst case 最不利输入下的复杂度
平均情况 average case 所有输入的平均复杂度
输入规模 input size 通常记作 n

⭐ 本章考点清单

  1. 算法的五个特性：有穷性、确定性、可行性、输入、输出
  2. 算法与程序的区别
  3. 大 O 记号含义：忽略常数与低阶项，只看增长趋势
  4. 单循环 O(n)、嵌套 O(n²)、砍半 O(log n) 的分析方法
  5. 空间复杂度：只算额外辅助空间；递归栈空间 O(n)
  6. 六大量级对比：O(1)/O(log n)/O(n)/O(n log n)/O(n²)/O(2ⁿ)
  7. 最好 / 最坏 / 平均情况，默认讨论最坏情况
  8. O、Ω、Θ 三种记号的语义（上界/下界/紧界）
  9. 时间换空间、空间换时间的权衡思想