algo01 复杂度分析与渐进记号 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个递进的任务，掌握复杂度分析的核心技能：代码复杂度推断、均摊分析实现、主定理应用、势能法分析。

预备知识

在开始练习前，确保你已经理解了以下概念（参见 demo.py 代码详解中的详细解释）：

大 O 记号的含义：忽略常数和低阶项，只关注增长率
常见循环模式的复杂度：单层循环 $O (n)$ 、嵌套循环 $O (n^{2})$ 、每次减半的循环 $O (\log n)$
均摊分析的基本思想：贵的操作被便宜的操作摊薄
主定理的三种情形及其适用条件

任务清单

任务1：分析代码复杂度

分析 func_a 到 func_e 五个函数的大 O 复杂度，将答案填入 TODO 注释中。

提示：

func_a：两个独立的循环，都是 $O (n)$ → 总复杂度
func_b：外层 $n$ 次，内层 $j$ 每次 $\times 2$ （即 $\log_{2} n$ 次） → 总复杂度
func_c：递推式 $T (n) = 2 T (n / 2) + O (1)$ → 应用主定理情形 1
func_d：外层 while 循环变量 $i$ 每次 $\div 2$ ，内层循环 $n$ 次 → 总复杂度
func_e：外层 $n$ 次，每次内层做二分查找 $O (\log n)$ → 总复杂度

任务2：模拟动态数组均摊分析

在 SimulatedDynamicArray.append() 方法中完成扩容逻辑：

当 size == capacity 时：
  1. capacity *= 2
  2. total_copies += size  (复制旧元素)
当 size < capacity 时：
  直接追加，不扩容

验证标准：运行 task2_simulate() 后：

最终均摊代价（total_copies / size）应 $\leq 2.0$
程序输出 ✅ 均摊代价验证通过！

任务3：主定理练习

分析五个递推式，确定 $a, b, \log_{b} (a)$ 以及属于主定理的哪种情形。

递推式	$a$	$b$	$\log_{b} a$	$f (n)$	情形	结果
$T (n) = 2 T (n / 2) + n$	2	2	1	$n$	2	$Θ (n \log n)$
$T (n) = T (n / 2) + 1$	1	2	0	$1$	2	$Θ (\log n)$
$T (n) = 3 T (n / 2) + n^{2}$	3	2	~1.585	$n^{2}$	3	$Θ (n^{2})$
$T (n) = 4 T (n / 2) + n$	4	2	2	$n$	1	$Θ (n^{2})$
$T (n) = T (2 n / 3) + 1$	1	3/2	0	$1$	2	$Θ (\log n)$

任务4（Bonus）：势能法验证

使用势能函数 $Φ = 2 \times s i z e - c a p a c i t y$ 计算每次 append 的均摊代价。

核心公式：

{\hat{c}}_{i} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})

其中 $c_{i}$ 是第 $i$ 次操作的实际代价， $Φ (D_{i})$ 是操作后数据结构的势能。

期望结果：每次 append 的均摊代价 ${\hat{c}}_{i}$ 恒为常数 3（无论是否发生扩容）。

势能法的直觉：

当数组不满时： $Φ$ 增加（储存势能），抵消了实际 $c_{i} = 1$ → 均摊后变 3
当数组满需要扩容时： $Φ$ 大幅减少（释放势能），抵消了实际 $c_{i} = 1 + s i z e$ → 均摊后还是 3

运行与验证

bash

cd algo01_complexity/code
python exercise.py

如果你的实现正确，应该看到：

任务1的分析与提示一致
任务2的均摊代价 $\leq 2.0$
任务4的势能法均摊代价恒为 3
所有 assert 断言通过

完整代码

# -*- coding: utf-8 -*-
"""
===============================================================================
algo01_complexity/code/exercise.py — 复杂度分析练习
===============================================================================
本练习文件中，你需要完成以下任务：
  1. 分析给定代码片段的复杂度（大 O 记号）
  2. 实现动态数组的均摊分析模拟
  3. 使用主定理分析分治算法的递推式
  4. 设计一个"势能法"均摊分析

运行方式：python exercise.py
===============================================================================
"""

import math
import time
import random


# ============================================================================
# 任务 1：分析代码复杂度（填写大 O 记号）
# ============================================================================

def analyze_complexity():
    """分析以下代码片段的复杂度，将你的答案填在注释中。"""
    print('========== 任务 1：复杂度分析 ==========')

    # TODO: 分析下面函数的复杂度，填入你的答案
    # 复杂度：O(____)
    def func_a(n):
        s = 0
        for i in range(n):
            s += i
        for j in range(n):
            s -= j
        return s

    # TODO: 复杂度：O(____)
    def func_b(n):
        s = 0
        for i in range(n):
            j = 1
            while j < n:
                s += 1
                j *= 2  # j 每次翻倍
        return s

    # TODO: 复杂度：O(____)
    def func_c(n):
        if n <= 1:
            return 1
        return func_c(n // 2) + func_c(n // 2)  # 两个递归调用

    # TODO: 复杂度：O(____)
    def func_d(n):
        s = 0
        i = n
        while i > 1:
            for j in range(n):
                s += 1
            i //= 2
        return s

    # TODO: 复杂度：O(____)
    def func_e(arr):
        # arr 是已排序的数组
        n = len(arr)
        for i in range(n):
            # 使用二分查找在 arr[i+1:] 中查找 -arr[i]
            lo, hi = i + 1, n - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if arr[mid] == -arr[i]:
                    return True
                elif arr[mid] < -arr[i]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False

    print('请将以上五个函数的大 O 复杂度填入 TODO 注释中。')
    print('提示：')
    print('  func_a: 两个独立的 O(n) 循环')
    print('  func_b: 外层 O(n)，内层 j 每次翻倍...')
    print('  func_c: T(n) = 2T(n/2) + O(1)，主定理...')
    print('  func_d: 外层 while 除以 2，内层 O(n)...')
    print('  func_e: 外层 O(n)，内层二分查找...')


# ============================================================================
# 任务 2：模拟动态数组的均摊分析
# ============================================================================

class SimulatedDynamicArray:
    """模拟动态数组，用于均摊分析。

    你需要完成 append 方法中的扩容逻辑。
    策略：当数组满时，扩容为原来的 2 倍。
    """

    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.total_copies = 0  # 累积复制次数

    def append(self, value):
        """
        TODO: 完成动态数组的 append 操作
        1. 如果 size == capacity，需要扩容（capacity *= 2）
        2. 扩容时，需要复制旧元素到新数组（计入 total_copies）
        3. 将新元素放入合适位置，size += 1
        """
        # TODO: 你的代码从这里开始
        if self.size == self.capacity:
            # 扩容
            self.capacity *= 2
            # 每次扩容需要复制 size 个旧元素
            self.total_copies += self.size

        # 追加元素（不需要真的存储值，只追踪 size 和 copies 即可）
        self.size += 1

    def amortized_cost(self):
        """返回均摊每次 append 的复制次数"""
        if self.size == 0:
            return 0
        return self.total_copies / self.size


def task2_simulate():
    """运行动态数组均摊分析模拟"""
    print('\n========== 任务 2：动态数组均摊分析 ==========')
    da = SimulatedDynamicArray()
    log = []

    for i in range(1, 65):
        da.append(i)
        if i % 8 == 0 or i < 4 or i == 64:
            log.append((i, da.capacity, da.total_copies, da.amortized_cost()))

    print(f'{"n":>4}  {"容量":>6}  {"总复制":>6}  {"均摊":>6}')
    for size, cap, copies, amort in log:
        print(f'{size:4d}  {cap:6d}  {copies:6d}  {amort:6.2f}')

    print(f'\n最终均摊代价: {da.amortized_cost():.4f} (应该 <= 2.0)')

    # TODO: 验证你的结果——均摊代价是否 <= 2？
    assert da.amortized_cost() <= 2.0, '均摊代价应 <= 2'
    print('✅ 均摊代价验证通过！')


# ============================================================================
# 任务 3：主定理练习
# ============================================================================

def task3_master_theorem():
    """使用主定理分析以下递推式，填写你的答案。

    递推式：T(n) = a * T(n/b) + f(n)

    TODO: 对每个递推式，确定 a, b, log_b(a)，以及属于哪种情形（1/2/3）
    """
    print('\n========== 任务 3：主定理练习 ==========')

    problems = [
        # (描述, a, b, f_n_description)
        ('归并排序: T(n) = 2T(n/2) + n', None, None, None),
        ('二分查找: T(n) = T(n/2) + 1', None, None, None),
        ('T(n) = 3T(n/2) + n²', None, None, None),
        ('T(n) = 4T(n/2) + n', None, None, None),
        ('T(n) = T(2n/3) + 1', None, None, None),
    ]

    print('请分析以下递推式（填写 a, b, log_b(a), 所属情形）：')
    for desc, _, _, _ in problems:
        print(f'  {desc}')
    print('\n提示：')
    print('  归并排序: a=2, b=2, log₂2=1, f(n)=n → 情形 2 → Θ(n log n)')
    print('  二分查找: a=1, b=2, log₂1=0, f(n)=1 → 情形 2 → Θ(log n)')
    print('  T(n)=3T(n/2)+n²: a=3, b=2, log₂3≈1.585, f(n)=n² → 情形 3 → Θ(n²)')
    print('  T(n)=4T(n/2)+n: a=4, b=2, log₂4=2, f(n)=n → 情形 1 → Θ(n²)')
    print('  T(n)=T(2n/3)+1: a=1, b=3/2, log_{3/2}1=0, f(n)=1 → 情形 2 → Θ(log n)')


# ============================================================================
# 任务 4（Bonus）：实现势能法分析
# ============================================================================

def task4_potential_method():
    """使用势能法分析动态数组（Bonus 任务）

    势能函数定义：Φ = 2 * size - capacity
    均摊代价：ĉ_i = c_i + Φ(D_i) - Φ(D_{i-1})

    你需要验证：当数组不满时，ĉ_i = 3（常数）
                 当数组满时（需要扩容），ĉ_i = 3（摊销后）
    """
    print('\n========== 任务 4（Bonus）：势能法分析 ==========')

    def potential(size, capacity):
        """TODO: 计算势能函数 Φ = 2 * size - capacity"""
        return 2 * size - capacity

    # 模拟 append 序列并计算势能法下的均摊代价
    capacity = 1
    size = 0
    amortized_costs = []

    for i in range(1, 33):
        phi_before = potential(size, capacity)
        actual_cost = 1  # 插入的基本代价

        if size == capacity:
            # 需要扩容
            actual_cost += size  # 复制 size 个旧元素
            capacity *= 2

        size += 1
        phi_after = potential(size, capacity)

        # TODO: 计算均摊代价 ĉ_i = actual_cost + phi_after - phi_before
        amortized_cost = actual_cost + phi_after - phi_before
        amortized_costs.append(amortized_cost)

    print(f'势能法分析结果（前 32 次 append）：')
    print(f'  均摊代价列表: {amortized_costs[:8]}...')
    print(f'  所有均摊代价: {set(amortized_costs)}')
    print(f'  最大均摊代价: {max(amortized_costs)}')
    print(f'  最小均摊代价: {min(amortized_costs)}')

    # 验证：均摊代价应该始终是常数（3）
    assert all(abs(c - 3.0) < 0.01 for c in amortized_costs), \
        f'均摊代价应为 3，实际值: {set(amortized_costs)}'
    print('✅ 势能法验证通过：每次 append 的均摊代价恒为 3！')


# ============================================================================
# 主函数
# ============================================================================

def main():
    print('=' * 60)
    print('  复杂度分析 — 练习程序')
    print('=' * 60)

    analyze_complexity()
    task2_simulate()

    # 检查均摊代价（你的实现是否正确？）
    da = SimulatedDynamicArray()
    for i in range(1000):
        da.append(i)
    expected_amortized = da.total_copies / 1000.0
    print(f'\n1000 次 append 后的均摊代价: {expected_amortized:.6f}')

    task3_master_theorem()
    task4_potential_method()

    print('\n✅ 所有练习已完成！')


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

algo01 复杂度分析与渐进记号 — exercise.py 练习指南 ​

练习目标 ​

预备知识 ​

任务清单 ​

任务1：分析代码复杂度 ​

任务2：模拟动态数组均摊分析 ​

任务3：主定理练习 ​

任务4（Bonus）：势能法验证 ​

运行与验证 ​

完整代码 ​