算法分析先回答两个问题：结果是否满足规格，输入变大时需要多少资源。测试能找到错误，证明需要说明所有满足前提的输入。先写清输入类型、允许的范围和空输入约定，再讨论复杂度，能避免把未定义行为当作算法缺陷。
从循环不变量到结束条件
下面返回每个前缀的最大值，并统计比较次数。处理下标 i 之前，不变量是：best 等于 values[:i] 的最大值，输出保存了前 i 个前缀的答案。初始化时只处理首元素，性质成立；加入新值时取较大者，性质保持。循环结束后 i 覆盖整个序列，所以得到全部答案。每轮处理一个新元素，剩余元素严格减少，终止性也有保证。
def prefix_maxima(values):
if not values:
return [], 0
best = values[0]
result = [best]
comparisons = 0
for index in range(1, len(values)):
value = values[index]
comparisons += 1
if value > best:
best = value
result.append(best)
return result, comparisons
if __name__ == '__main__':
print(prefix_maxima([3, 1, 5, 5]))
[3, 1, 5, 5] 输出 [3, 3, 5, 5]，比较三次。若先把 best 初始化为零，输入 [-4, -2] 会立刻成为反例。空列表返回空结果，无须假造一个“最大值”。
成本模型决定结论
在元素比较按常数时间计费的模型下，长度为 n 时恰好比较 n-1 次，时间为 Θ(n)，输出空间为 Θ(n)，除输出外只用常量状态。O(n) 是上界，Ω(n) 是下界，Θ(n) 表示两者匹配；不能把 O 一律解释成“最坏情况”，最好、最坏和平均情况也都可以分别给渐近界。
Python 大整数的位数会影响算术和比较成本。若键本身是长字符串，比较不能不加说明地计为常数。输入规模还可能是图的 V+E、矩阵的行列或输入整数的位数，不总是一个列表长度。
两层循环不一定 Θ(n²)：内层每次减半时需要求和。归并排序可写成 T(n)=2T(n/2)+Θ(n)，每层合并总工作 Θ(n)，共有 Θ(log n) 层，因此 Θ(n log n)。分析递归空间时沿同一时刻的调用栈计数，不能直接累加所有调用。
摊还与期望分开看
动态数组扩容时可能复制全部旧元素，单次追加会很贵；容量按倍数增长时，连续 m 次追加累计复制量是一个几何级数，总成本 O(m)，所以每次摊还 O(1)。这是对一段操作序列的确定性结论，不要求随机输入。
随机快排的期望 O(n log n) 则来自随机选择。最坏情况仍可能 O(n²)，随机化改变发生概率，并没有删去坏情况。做工程判断时还要看内存、常数与输入分布。
自己检查
给前缀函数加一个“每个前缀都重新调用 max”的基线，计算总比较次数 0+1+...+(n-1)。再证明两者输出相同。测试包含空序列、单元素、全负数、全相同和严格递增输入；性能测量前先用这些用例确认含义一致。
面试自查
- 为什么
best=0不满足初始化要求？因为零不一定属于已处理输入，也不保证是其最大值。 - O(n) 时间是否表示只扫描一次？不是；多次固定次数扫描仍为 O(n)。
- 递归树节点数与峰值空间为什么不同？调用可先后释放，只有同时存活的状态占据峰值空间。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。