从代码判断效率,可以先数一个明确的基本操作,再看输入扩大时次数怎样增长。同时还要检查:运行时额外保存了多少数据?

本文使用Python循环、数组和递归建立时间与空间分析的方法。读者需要熟悉变量、列表、循环和函数。

上一篇:导论。下一篇:渐进符号与函数增长率。

1. 输入规模与基本操作

数组可用元素个数n作为规模;字符串问题可能有两个长度m、n;图问题常同时需要顶点数和边数。

整数N的数值与其编码长度不同。正整数N的二进制位数为 $\lfloor\log_2 N\rfloor+1$,所以循环N次与循环编码位数次的资源需求不同。

以下将一次比较、索引、交换或计数更新作为基本操作,采用单位代价模型;空间以同时存活的变量或元素槽位衡量。若计算大整数的实际位运算成本,还需按整数位数进一步分析。

1.1 寻找最大值

def maximum(values):
    if not values:
        raise ValueError("Expected a nonempty list")
    best = values[0]
    for i in range(1, len(values)):
        value = values[i]
        if value > best:
            best = value
    return best

当数组有5个元素时,比较4次;有100个元素时,比较99次。如果只统计 value > best 的执行次数,就有:

$$ C(n)=n-1,\qquad n\ge 1 $$

注意这里统计的是一种操作的次数,不是所有机器指令的精确总数。做复杂度分析前,要说清楚采用的模型和统计对象。

这段实现按下标读取数组,只保存下标、当前值和当前最大值,使用常数额外空间。

整个函数还执行索引和赋值,但这些操作也只随n线性增长。

1.2 怎样使用复杂度记号

O给出增长上界;Θ表示与某个函数同阶,即上下都能被该函数的固定倍数夹住。例如n−1次比较随n线性增长,总时间Θ(n),也可以给出上界O(n)。

本篇先从具体次数理解这些记号,严格的常数和量词定义见渐进符号篇。

2. 六种循环的代码计数

下面统计count += 1的次数,时间结论也计入循环控制和初始化,沿用单位代价模型。空间不计输入与返回标量。

2.1 单层循环

def single_count(n):
    count = 0
    for _ in range(n):
        count += 1
    return count

assert single_count(4) == 4

操作次数 $C(n)=n$,时间Θ(n),额外空间O(1)。

2.2 顺序执行的两个循环

def sequential_count(n):
    count = 0
    for _ in range(n):
        count += 1
    for _ in range(n):
        count += 1
    return count

assert sequential_count(4) == 8

操作次数 $C(n)=n+n=2n$,时间Θ(n),额外空间O(1)。顺序执行的工作量相加。

2.3 完全嵌套

def square_count(n):
    count = 0
    for _ in range(n):
        for _ in range(n):
            count += 1
    return count

assert square_count(4) == 16

每轮内层n次,外层n轮:$C(n)=n^2$。时间Θ(n²),额外空间O(1)。执行n²次操作,并没有同时保存n²个元素。

2.4 三角形循环

def triangular_count(n):
    count = 0
    for i in range(1, n + 1):
        for _ in range(i):
            count += 1
    return count

assert triangular_count(4) == 10

n=4时,四轮分别执行1、2、3、4次,共10次。

三角形循环逐行计数

$$ C(n)=\sum_{i=1}^{n}i=\frac{n(n+1)}2=\frac12n^2+\frac12n $$

求和表示把每轮次数相加。时间Θ(n²),额外空间O(1)。

进阶阅读:求和式的归纳证明

n=1时成立。假设前k项之和为 $k(k+1)/2$,加上k+1得到:

$$ \frac{k(k+1)}2+(k+1)=\frac{(k+1)(k+2)}2 $$

这正是下一规模的公式,因此等式对所有正整数成立。

2.5 i每轮翻倍

def doubling_count(n):
    count = 0
    i = 1
    while i <= n:
        count += 1
        i *= 2
    return count

assert doubling_count(16) == 5
assert doubling_count(0) == 0

访问1、2、4、8、16,共5次。第k次翻倍后为 $2^k$;要进入循环,需 $2^k\le n$。因此:

$$ C(n)=\lfloor\log_2n\rfloor+1\qquad(n\ge1) $$

时间Θ(log n),额外空间O(1)。n=0直接返回。折半查找缩小候选区间的过程具有同样的对数结构,见查找文章。

2.6 外层线性、内层对数

def linear_log_count(n):
    count = 0
    for _ in range(n):
        i = 1
        while i <= n:
            count += 1
            i *= 2
    return count

assert linear_log_count(4) == 12

每轮把i重置为1,操作次数 $n(\lfloor\log_2n\rfloor+1)$(n≥1),时间Θ(n log n),额外空间O(1)。

2.7 核对计数

for n in (1, 4, 16):
    triangle = triangular_count(n)
    doubling = doubling_count(n)
    assert triangle == n * (n + 1) // 2
    assert doubling == n.bit_length()
    print(n, triangle, doubling)

输出:

1 1 1
4 10 3
16 136 5

3. 时间与空间是两个维度

3.1 三种空间口径

输入空间是调用前提供的数据;辅助空间是运行额外保存的变量、临时数组与调用栈;输出空间是返回结果所需的结构。

本文“额外空间”指输入之外的空间,并说明输出是否计入。分析的是同时存活数据的峰值。

3.2 对比三个实现

第1节maximum只保存几个变量,时间Θ(n),额外空间O(1)。

复制输入则要创建新列表:

def copy_values(values):
    copied = []
    for value in values:
        copied.append(value)
    return copied

assert copy_values([3, 1, 4]) == [3, 1, 4]

append在摊还意义下为常数时间,n次添加共Θ(n)时间。新列表保存n个引用;计入返回列表时额外空间Θ(n)。若只计辅助空间,则辅助O(1),输出Θ(n)。这是浅复制,元素对象本身没有逐个复制。

再创建长度n的临时数组:

def count_above_average(values):
    n = len(values)
    if n == 0:
        return 0
    average = sum(values) / n
    flags = [0] * n
    for i in range(n):
        flags[i] = int(values[i] > average)
    return sum(flags)

assert count_above_average([1, 2, 6]) == 1

两次求和、初始化与扫描均为线性,总时间Θ(n),辅助数组flags占Θ(n),输出是一个计数。

程序 时间 额外空间(含输出) 原因
maximum Θ(n) O(1) 几个变量
copy_values Θ(n) Θ(n) 新列表是输出
count_above_average Θ(n) Θ(n) 临时标记数组

[0] * n只有一行,初始化n个槽位仍需Θ(n)时间和空间。循环是O(n),并不意味着空间也是O(n)。

4. 指数与阶乘:候选数量如何增长

4.1 O(1):固定数量的访问

def first_or_none(values):
    return values[0] if values else None

assert first_or_none([8, 3]) == 8

对普通Python列表,只检查长度并访问第一项,时间、辅助空间均为O(1)。

4.2 O(2ⁿ):每项选或不选

每个元素有两种状态,n个元素有 $2^n$ 个子集。n为10、20、40时,数量依次为1,024、1,048,576、1,099,511,627,776。

代码训练:二叉递归的叶子数量
def subset_leaves(n):
    if n < 0:
        raise ValueError("Expected n >= 0")
    if n == 0:
        return 1
    return subset_leaves(n - 1) + subset_leaves(n - 1)

assert subset_leaves(4) == 16

叶子共 $2^n$ 个,总调用数 $2^{n+1}-1$,时间Θ(2ⁿ)。两支依次执行,递归深度n,因此辅助空间O(n)。

若要复制每个长度n的选择向量,还需Θ(n2ⁿ)时间。候选数量与检查候选的成本要分别分析。

4.3 O(n!):排列

n个不同元素的排列有 $n!=n(n-1)\cdots1$ 个。

代码训练:原地交换统计排列
def permutation_leaves(n):
    if n < 0:
        raise ValueError("Expected n >= 0")
    values = list(range(n))
    count = 0

    def visit(start):
        nonlocal count
        if start == n:
            count += 1
            return
        for i in range(start, n):
            values[start], values[i] = values[i], values[start]
            visit(start + 1)
            values[start], values[i] = values[i], values[start]

    visit(0)
    return count

assert permutation_leaves(4) == 24
assert permutation_leaves(0) == 1

深度k的调用有 $n!/(n-k)!$ 个。因为 $\sum_{j=0}^n1/j!<3$,总调用数介于n!与3n!之间,每条树边只作常数次交换,时间Θ(n!)。

列表与调用栈各占O(n),辅助空间O(n)。若把每个完整排列复制到输出,时间与输出空间变为Θ(nn!)。

4.4 常见复杂度对照

上界 对应代码 主要工作量 额外空间
O(1) first_or_none 固定访问 O(1)
O(log n) doubling_count 翻倍轮数 O(1)
O(n) maximum、single_count 扫描n项 O(1)
O(n log n) linear_log_count n轮对数循环 O(1)
O(n²) square_count、triangular_count 二次求和 O(1)
O(2ⁿ) subset_leaves 二叉树节点 O(n)栈
O(n!) permutation_leaves 排列树节点 O(n)

树的总节点数与同时存活的路径长度,分别影响时间与栈空间。

5. 最好、最坏与平均情况

def linear_search_count(values, target):
    comparisons = 0
    for i, value in enumerate(values):
        comparisons += 1
        if value == target:
            return i, comparisons
    return -1, comparisons

assert linear_search_count([7, 3, 9], 7) == (0, 1)
assert linear_search_count([7, 3, 9], 5) == (-1, 3)

固定非空数组长度n,最好情况是第一项命中,比较1次;最坏情况是最后命中或不存在,比较n次。

平均情况需要概率模型。假设目标一定存在、元素互异,每个位置命中的概率均为1/n,则期望次数为:

$$ \frac{1+2+\cdots+n}{n}=\frac{n+1}2 $$

改变未找到的概率或各位置概率,平均值也会改变。这里首尾平均来自均匀分布。O(n)本身只给上界,既可以描述最坏函数,也可以描述平均函数。

6. 常数、低阶项与实际秒数

考虑两种工作量:

$$ A(n)=100n,\qquad B(n)=n\log_2 n $$

当 $n=16$ 时,前者是1600,后者是64,B 更少。但当 $n>2^{100}$ 时,$\log_2 n>100$,A 反而更少。

所以渐进分析关注的是:当 n 足够大后,工作量以什么速度增长,而不是宣称在所有规模上某种算法都更快。常数在实际运行中仍然重要,只是在讨论增长阶时被统一吸收。

对照一下翻倍的效果:

工作量 n 变成 2n 后,与原来的比值
$n$ 2
$n^2$ 4
$n^3$ 8
$2^n$ $2^n$,不是固定常数

更多增长比较见渐进符号篇。

$n^2+100n$ 与 $2n^2$ 都是二次阶;n>100时前者更小。舍去常数和低阶项,是在概括增长速度,不是把精确次数当作相等数值。

7. 易错点

  • 顺序循环次数相加,嵌套循环按每轮实际次数求和。
  • 两层循环可以是n²、n log n或其他阶。
  • 翻倍产生对数轮数,步长加2仍是线性。
  • 代码行数不代表操作次数,库函数、切片和初始化也有成本。
  • 时间统计全部工作,空间统计同时存活的数据。
  • 实际秒数反映运行条件,复杂度反映规模增长。

8. 练习

前四题统计count += 1次数,n为非负整数;空间不计输入。

练习1:步长为2

def exercise_step(n):
    count = 0
    for _ in range(0, n, 2):
        count += 1
    return count

n=7时是多少?一般公式是什么?

练习2:顺序执行

def exercise_sequential(n):
    count = 0
    for _ in range(n):
        count += 1
    for _ in range(3 * n):
        count += 1
    return count

写出精确次数。

练习3:严格下三角

def exercise_triangle(n):
    count = 0
    for i in range(n):
        for _ in range(i):
            count += 1
    return count

与第2.4节相比少几次?

练习4:严格小于n

def exercise_double(n):
    count = 0
    i = 1
    while i < n:
        count += 1
        i *= 2
    return count

n=1、8、9时各几次?给出n≥1的公式。

练习5:时间分析

先做n次操作再做n²次,与外层n次、内层n²次,各有多少次操作,属于什么时间阶?

练习6:线性对数

linear_log_count内层改为i < n,次数是多少?若外层不重置i,工作量如何变化?

练习7:复制列表

copy_values计入输出时的时间与额外空间是什么?只统计辅助空间时如何单列输出?

练习8:复用辅助数组

def exercise_scratch(n):
    total = 0
    scratch = [0] * n
    for i in range(n):
        for j in range(n):
            scratch[j] = i + j
        total += scratch[0] if n else 0
    return total

分析时间和辅助空间,说明为什么不保存n²项数据。

9. 参考答案

  1. n=7时4次,一般 $\lceil n/2\rceil$,时间Θ(n),空间O(1)。
  2. $n+3n=4n$,时间Θ(n),空间O(1)。
  3. $n(n-1)/2$,少n次;时间Θ(n²),空间O(1)。
  4. 分别0、3、4次,n≥1时为 $\lceil\log_2n\rceil$。循环边界影响精确次数。
  5. 顺序执行 $n+n^2\in\Theta(n^2)$,嵌套执行 $n^3\in\Theta(n^3)$;只用计数器时空间均为O(1)。
  6. 次数为 $n\lceil\log_2n\rceil$。若i跨轮次延续,只在第一轮完成翻倍,但仍有n轮外层控制,总时间Θ(n+log n)=Θ(n)(n≥2)。
  7. 时间Θ(n);含输出时额外空间Θ(n),只计辅助则O(1)、输出Θ(n)。
  8. 初始化Θ(n),赋值n²次,总时间Θ(n²);scratch仅一份长度n的列表,空间Θ(n)。每轮覆盖旧值,没有保存此前所有轮次。

可以用AI助手逐题检查统计对象、次数公式和空间口径,再用小输入运行核对。

10. 后续学习与资料

下一篇:渐进符号与函数增长率给出严格定义和比较方法,之后在贪心算法中分析实际求解程序。

参考:《Design and Analysis of Algorithms》第二讲02Analysis,第2至13页的运行时间与规模,第15至26页的渐进语言,第42页的位运算模型。三角循环、翻倍计数和100n对比沿用原笔记,空间与代码训练在此展开。

相关主题














算法复杂度分析基础:从代码计数到时间与空间复杂度。























渐进符号与函数增长率:Big-O、Ω、Θ 与严格比较。













贪心算法入门:从局部选择到全局最优证明。