2. 算法与复杂度：如何衡量「快」

从「查字典」理解复杂度

在一个有 100 万条的有序列表里找目标：

• 线性查找：从头一个个看，最坏 100 万次 —— O(n)
• 二分查找：每次看中间元素，排除一半，最多约 20 次 —— O(log n)

差距的直觉：数据翻倍，线性查找耗时翻倍，二分查找只多 1 步。这就是时间复杂度——描述增长趋势，而不是运行秒数。

常见复杂度速查

大 O	名字	典型例子	n = 1,000,000 时大约操作数
O(1)	常数	字典按键取值	1
O(log n)	对数	二分查找	~20
O(n)	线性	遍历数组	1,000,000
O(n log n)	线性对数	高效排序	~20,000,000
O(n²)	平方	双重循环	1,000,000,000,000

二分查找的实现

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1     # 目标在右半边
        else:
            hi = mid - 1     # 目标在左半边
    return -1

前提只有一个：nums 必须有序——「比中点小就一定在左半边」这个推理依赖有序性。

空间换时间

发现程序慢时，两个常用大招：

1. 换数据结构：if x in list 是 O(n)，换 set 就是 O(1)。
2. 预计算缓存：把重复计算的结果存起来，一次计算多次使用。

💡 一句话总结：先选对复杂度，再谈代码优化——数据量一大，O(n²) 写得再精妙也跑不过 O(n log n)。