Week 4 学习成果｜Big-O 与四类基础算法

本篇与一年学习计划总纲 Phase I 的 Week 4 · 算法与复杂度 一致，按总纲「每周固定执行模板」编排。Week 4 暂无单独的计划篇，本篇先记录实际成果。

🎯 本周目标

L3

• ✅ 能判断时间复杂度、空间复杂度与最坏情况

📚 Core Knowledge

• Big-O 与复杂度增长阶梯，最坏 / 平均 / 最好情况的区别
• 递归与分治的直觉
• 线性搜索、二分查找
• 插入排序、归并排序

✍️ Human Core

• 手写线性搜索
• 手写二分查找
• 手写插入排序
• 手写归并排序

🧪 Experiment

Hypothesis

• 运行时间由「常数」和「增长阶」共同决定：小规模时常数可能反超，规模变大后 Big-O 主导。

Experiment

• 比较 O(n) / O(n log n) / O(n²) 三类算法在不同数据规模下的运行表现。

Result

• 小规模下常数小的实现更快；规模增大后，增长阶低的一方稳定胜出。

Conclusion

• 常数决定起跑线，Big-O 决定天花板。

📝 数智工程师考试映射

• 时间 / 空间复杂度分析与最坏情况
• 基础排序与查找算法

✅ Acceptance

• 能判断常见算法的时间、空间复杂度与最坏情况
• 能说清二分查找为什么要求数据有序、复杂度为何是 O(log n)

🧠 本周最重要的问题

常数和 Big-O，各自在什么规模下决定胜负？

小数据量时循环常数和分支开销占主导，写法更朴素的 O(n²) 可能更快；一旦规模放大，增长阶更低的一方必然反超。所以选算法先看增长阶，再看常数。

❓ 尚未解决

• 归并排序的递归栈空间分析、快排的最坏情况还没展开。
• 复杂度只到「会判断」，没有系统推导过均摊分析。

📊 Final Level

L3

复杂度增长阶梯

默认用最坏情况分析：同一个算法，最好 / 平均 / 最坏常常不是同一阶。

四种算法

# 线性搜索 O(n)
def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

# 二分查找 O(log n)，要求已排序
def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# 插入排序 O(n²)，近乎有序时接近 O(n)
def insertion_sort(a):
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

# 归并排序 O(n log n)，稳定
def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

实验结论

小数据量时，常数小、循环更简单的插入排序可能反超归并排序；数据量一放大，O(n log n) 就稳定压过 O(n²)。常数决定起跑线，Big-O 决定天花板。

来源与延伸阅读

• Big-O Cheat Sheet
• Python Sorting HOWTO
• bisect — 数组二分算法