📑 本页目录(点开跳转)
04 · 二分、排序与堆:怎样少看一半
⏱ 13 分钟 | 边界二分、旋转数组最小值、最小的 k 个数、复杂度增长
🎯 一句话
二分不是“猜中间数”,而是每一轮都能确定:答案还在左半还是右半。
🧩 题 1:升序数组中数字出现的次数
不要一个个数。找第一次出现的位置,再找第一次“大于目标”的位置;两者相减就是次数。
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
def count_target(nums, target):
return lower_bound(nums, target + 1) - lower_bound(nums, target)
assert count_target([1, 2, 2, 2, 3, 4], 2) == 3
assert count_target([1, 2, 3], 9) == 0
不变量:[0, left) 中都小于 target,[right, n) 中都大于等于 target;待判断元素位于 [left, right)。最终边界是 left == right,可能等于 n,因此插入位置属于闭区间 [0, n],不能说答案始终是半开区间里的元素。
🧩 题 2:旋转数组的最小数字
数组有重复值时,nums[mid] == nums[right] 不能判断最小值在哪半边;只将 right 减一,仍保留一个可能的最小值。无重复时每轮大致减半,是 O(log n);大量重复时最坏退化到 O(n)。空数组没有最小值,下面显式拒绝。
def min_in_rotated(nums):
if not nums:
raise ValueError("empty sequence")
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1 # 相等时无法判断哪半边,安全地缩小一个位置
return nums[left]
assert min_in_rotated([3, 4, 5, 1, 2]) == 1
assert min_in_rotated([1, 2, 3]) == 1
assert min_in_rotated([1, 1, 0, 1]) == 0
🧩 题 3:最小的 k 个数
当你只要前 k 个,不必把全部排好。Python 的最小堆直接拿前 k 个最小元素。
import heapq
def smallest_k(nums, k):
if not 0 <= k <= len(nums):
raise ValueError("k out of range")
return heapq.nsmallest(k, nums)
assert smallest_k([4, 5, 1, 6, 2, 7, 3, 8], 4) == [1, 2, 3, 4]
⚠️ 面试若要求手写,可用“大小为 k 的最大堆”;但先把“只维护 k 个候选”这个思想弄懂。
可选深入:同一处分区,递归与显式栈怎么写?
只把还没排好的区间交出去
本节的堆是在“只取 k 个”时少做工作;下面则假设需要完整排序,用快排作一个可跳过的对照。分区选末元素作 pivot,扫描时保持 [lo,i) ≤ pivot、[i,j) > pivot;最后把 pivot 放到 i,它就不再进入任何子问题。两种调度共用这一份分区,不要把分区边界和递归边界混用。
def partition(a, lo, hi): # inclusive endpoints
pivot, i = a[hi], lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return i
def quick_recursive(values):
a = list(values) # convenience copy; partition itself works in-place
def visit(lo, hi):
if lo >= hi:
return
p = partition(a, lo, hi)
visit(lo, p - 1)
visit(p + 1, hi)
visit(0, len(a) - 1)
return a
def quick_stack(values):
a = list(values)
pending = [(0, len(a) - 1)]
while pending:
lo, hi = pending.pop()
if lo >= hi:
continue
p = partition(a, lo, hi)
if lo < p - 1:
pending.append((lo, p - 1))
if p + 1 < hi:
pending.append((p + 1, hi))
return a
from itertools import product
for n in range(8):
for values in product((-1, 0, 1), repeat=n):
expected = sorted(values)
assert quick_recursive(values) == expected
assert quick_stack(values) == expected
for values in (list(range(30)), list(range(30))[::-1], [7] * 30):
assert quick_recursive(values) == quick_stack(values) == sorted(values)
print("空/单元素/重复/有序/逆序与短数组穷举通过")
每次分区线性扫描当前区间;分得均衡时总工作 O(n log n),但这个固定末元素版本遇到已排序、逆序或全相同输入会退化到 O(n²)。递归深度最坏 O(n),在 Python 中还可能超过递归限制;显式栈移除了函数递归,没有自动消除坏分区,一般仍按最坏 O(n) 辅助调度空间估计。教学函数还额外复制了 O(n) 结果数组;两者都不是稳定排序。随机选 pivot 可改善期望行为,三路分区可改善大量重复值,但不在本小例展开。
依据作者教材:Open Data Structures:比较排序与快排。这里验证排序结果与边界,不提供生产排序性能结论。
📈 输入翻倍,时间为什么可能变四倍?
先看一个现象:同一个程序处理 200 个数据用了 200 秒。如果可用时间增加到 800 秒,能不能直接把输入也增加到 800 个?先别急着按比例乘四——答案取决于输入变大时,算法要做的工作怎样增长。
时间复杂度(Time Complexity)不是秒表读数。它比较的是:当输入规模 n 变大时,算法的主要操作次数按什么趋势增长。复杂度是在比较“输入变大后,工作量怎么长”,而墙上时钟测到的运行时间还会受机器、实现、缓存和当时负载影响。
- O(n²) 读作“大 O 的 n 平方”。大 O 只给增长上界:输入足够大后,工作量不会超过某个常数乘以 n²;它不是精确等式,也不保证二次项在当前输入范围内已经占主导。因此,不能只凭 O(n²) 推出输入翻倍就必然四倍。
- ≈ 读作“约等于”,表示两边在当前假设下足够接近,但不要求完全相等。它和表示严格相等的
=不同。 - n² 就是
n×n。例如 n 从 2 变成 4,n² 从 4 变成 16,也就是 4 倍。
先把线性增长和平方增长摆在一起
| 输入规模 | 线性项主导的教学模型 工作量 ≈ cn | 二次项主导的教学模型 工作量 ≈ cn² | 直觉 |
|---|---|---|---|
| n | n(1 倍) | n²(1 倍) | 作为比较起点 |
| 2n | 2n(2 倍) | 4n²(4 倍) | 在二次项主导模型里,输入翻倍对应约四倍工作 |
| 4n | 4n(4 倍) | 16n²(16 倍) | 在二次项主导模型里,输入变四倍对应约十六倍工作 |
读表时只比较教学模型里的倍数:线性增长看“一条边”,平方增长可想成正方形的长和宽一起变大。表格使用的是“线性项或二次项已经主导”的近似模型;不能从一个 O(...) 上界直接推出精确比例,更不是在声称每次运行都会精确花同样的秒数。
在二次项主导的模型中估算 800 秒能处理多少
要做下面的估算,不能只知道这个程序的上界写成 O(n²)。还必须假设两次运行使用同一台机器、同一份实现,输入足够大,并且从 200 个到待估规模这一段里,二次项确实压过固定开销和低次项。核心前提是:我们讨论的是二次项主导、可近似写成 t≈cn² 的输入区间;不是只看到 O(n²) 就套比例。
$$t \approx c n^2$$
n:输入规模,也就是要处理的数据个数。t:在上述条件下测得的运行时间。c:机器速度、实现细节等合在一起的比例常数;同条件比较时,近似认为它不变。- 在这类典型 O(n²) 工作中,可以把它看成:大约 n 个输入,每个又触发大约 n 次操作,于是得到 n×n;但双重循环不一定都是 O(n²),仍要看循环实际执行次数。
第一次运行是 (n₁, t₁),第二次运行是 (n₂, t₂)。两式相除,公共的 c 被约掉:
$$\frac{t_2}{t_1}\approx\frac{c n_2^2}{c n_1^2}=\left(\frac{n_2}{n_1}\right)^2$$
这里继续用 ≈,因为 t≈cn² 本来就是二次项主导时的近似模型,而不是精确计时公式。
现在完整代入 n₁ = 200、t₁ = 200 秒、t₂ = 800 秒:
$$\frac{800}{200}=4\approx\left(\frac{n_2}{200}\right)^2$$
令 r = n₂ / 200,问题就变成 4 ≈ r²。平方根是在问:“哪个非负数自己乘自己得到 4?”因为 2×2=4,所以 4 的非负平方根是 2。虽然 (-2)×(-2) 也等于 4,但 r 是两个输入规模的比值,负的输入规模比例没有意义,因此这里只取非负的 2:
$$2\approx\frac{n_2}{200}\quad\Rightarrow\quad n_2\approx 2\times200=400$$
结论:仅在相同运行条件、且 200 到 400 这个输入区间可用
t≈cn²描述时,时间预算变成 4 倍才对应输入规模约变成 2 倍,也就是约 400 个,不是 800 个。O(n²) 上界本身不够推出这个比例。
失败案例:把近似公式当成精确秒表
大 O 只给增长上界,不证明当前输入区间已经由二次项主导。如果输入只有几个元素,程序启动、函数调用、内存分配等固定开销可能比算法主体还显眼;换机器、换语言实现、缓存命中不同,甚至后台任务变化,也会改变墙上时钟时间。因此“工作量约四倍”不保证某次实测一定恰好从 200 秒变成 800 秒。这个比例估算只适合在同条件、同实现、较大输入且二次项主导时判断增长量级。
✍️ 预测练习:同条件且二次项主导时,时间预算变成 9 倍,输入能变成几倍?
只有在所比较的输入区间仍可近似写成 t≈cn² 时,才先写 9 ≈ (n₂ / n₁)²。3 是 9 的非负平方根,因为 3×3=9;输入规模比值不能为负,所以 n₂ / n₁ ≈ 3。若原来处理 200 个,大约可处理 600 个,而不是 1800 个。仅知道 O(n²) 上界时不能得出这个比例。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 07 · 启发式与 A* | ⭐ 题 3 的 heapq 换个场景就是 A* 的心脏:按 $f = g + h$ 最小取出下一个节点,用的就是同一个最小堆 |
本节回顾
二分每轮都删掉一半,前提是你说得出删掉那一半为什么不可能有答案。
✅ 检查点
为什么 lower_bound 的右边界写成 len(nums) 而不是 len(nums)-1?
👀 看答案
因为要表达“目标比所有元素都大”时的插入位置;半开区间也让空数组和边界判断统一。
同一份程序在相同运行条件下,并且 300 到 600 这个输入区间的主要工作可近似写成 t≈cn²。输入从 300 个增加到 600 个时,主要工作量大约变成多少倍?为什么只知道 O(n²) 上界还不够?
👀 看答案
在题目明确给出的二次项主导近似下,输入变成 2 倍,主要工作量约变成 2² = 4 倍。O(n²) 只表示增长上界,并不保证当前区间由二次项主导;实际运行时间还受常数、缓存、实现、系统负载和固定开销影响,所以这个 4 倍仍不是精确计时承诺。
⚡ 走神救援
- 二分找的是边界,不只是值。
- 旋转数组用
mid和右端比较,确认最小值在哪半边。 - 只要前 k 个:维护 k 个候选,不要先全排序。
- 只有在同条件、且当前输入区间可近似写成
t≈cn²时,时间预算变 4 倍才对应输入规模约变 2 倍;O(n²) 上界本身不够。