模块 05: 算法与效率

计数前明确输入规模与操作。n 个固定大小键的线性搜索最多 n 次比较。O 是常数倍意义下、超过某阈值后的渐近上界，Ω 是下界，Θ 同时是两者。3n+7 为 Θ(n)，固定项与常数不改变增长阶；称其 O(n²) 也正确但不紧。需说明分析哪种情况，不能把符号自动等同于最坏情况。

二分搜索要求键有序且支持高效索引。维护半开区间 [lo,hi)，初始 [0,n)，检查中点。寻找首个匹配时，中点键较小则 lo=mid+1，否则 hi=mid，保留左侧可能相等项。lo=hi 时检查插入位置。每次探测大致减半，探测次数 O(log n)。对一次查询先排序可能比线性扫描更贵。

迭代 i 前，前缀 [0,i) 已排序且恰含原前缀项目。取第 i 项为键，把更大项右移，再插入空位，保持不变式。只移动严格更大的键可保留相等键顺序，称稳定排序。有序输入比较 n−1 次，逆序输入比较 n(n−1)/2 次。复制输入版本还分配 n 项输出。

归并排序分割、递归排序并线性合并，通常最坏比较为 Θ(n log n)，合并存储 O(n)。快速排序按枢轴划分，典型平均 Θ(n log n)，差枢轴可达 Θ(n²)。比较排序区分 n! 种排列，最坏需 Ω(log₂(n!))=Ω(n log n) 次比较。计数排序利用受限整数键，因此不违背比较模型下界。

区分输入、输出与辅助工作空间。迭代二分搜索辅助状态 O(1)，递归版本栈空间 O(log n)。最佳、最坏、平均依赖不同输入假设，平均需要分布。基准测量需等价输出、可比数据与重复运行。计数揭示增长，耗时揭示常数与环境；两者都不能替代正确性检查。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m05_search.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

运行前手动跟踪 lo、hi。probes 统计区间探测，最后相等检查另算。

下载 m05_search.py

"""Binary search maintains a half-open candidate interval [lo, hi)."""
def binary_search(items, target):
    lo, hi, probes = 0, len(items), 0
    while lo < hi:
        mid = (lo + hi) // 2
        probes += 1
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    found = lo if lo < len(items) and items[lo] == target else -1
    return found, probes

for size in [0, 1, 8, 16, 32]:
    items = list(range(size))
    found, probes = binary_search(items, size)
    assert found == -1
    print(f"n={size:2}, absent insertion point={size:2}, probes={probes}")
assert binary_search([1, 2, 2, 4], 2)[0] == 1
assert binary_search([], 1) == (-1, 0)
print("duplicate case returns first match")

n= 0, absent insertion point= 0, probes=0
n= 1, absent insertion point= 1, probes=1
n= 8, absent insertion point= 8, probes=3
n=16, absent insertion point=16, probes=4
n=32, absent insertion point=32, probes=5
duplicate case returns first match

1. 查询十六项的每个值。
2. 尝试 [2,1] 并说明假设违反。
3. 把 hi=mid 改为 mid−1，找遗漏边界。

检查空、重复、有序与逆序输入的排序输出。

下载 m05_sort.py

"""Insertion sort counts key comparisons, not elapsed seconds."""
def insertion_sort(values):
    result = values.copy()
    comparisons = 0
    for i in range(1, len(result)):
        key, j = result[i], i - 1
        while j >= 0:
            comparisons += 1
            if result[j] <= key:
                break
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result, comparisons

for values in [[], [1], [1, 2, 3, 4], [4, 3, 2, 1], [2, 1, 2]]:
    result, count = insertion_sort(values)
    assert result == sorted(values)
    print(values, "->", result, "comparisons:", count)

[] -> [] comparisons: 0
[1] -> [1] comparisons: 0
[1, 2, 3, 4] -> [1, 2, 3, 4] comparisons: 3
[4, 3, 2, 1] -> [1, 2, 3, 4] comparisons: 6
[2, 1, 2] -> [1, 2, 2] comparisons: 2

1. 运行逆序长度八和十六。
2. 跟踪相同键的原位置。
3. 解释复制的内存成本。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• MIT 算法课程 — 阅读排序与二分资料，指出各自前置条件。

跟踪五项二分，说明每次丢弃区间的理由，陈述插入排序不变式。模块 06 将研究表示如何影响操作成本。