COMPLEXITY EXPLORER

同样是增长，速度大不相同。

拖动输入规模 n，把抽象的 Big O 变成直观的工作量。先问算法做了多少工作，再看它随输入如何增长。

输入规模 · 拖动探索n = 1,000

一张图，看清增长的分野

横轴是 n 的对数刻度；纵轴是 log₁₀(操作量)。超过 10¹² 的曲线在顶部截断，完整量级见下方数值。点击图例可隐藏曲线。

O(1)1数组下标访问

O(log n)10二分查找

O(n)1,000遍历数组

O(n log n)9,966归并排序

O(n²)1,000,000双重枚举

O(2ⁿ)≈ 10^301枚举所有子集

O(n!)≈ 10^2,568枚举所有排列

这些数值是去掉常数后的增长模型，不是实际耗时预测；log 的底数取 2，n=1 时按至少一次操作显示。阶乘在大 n 时使用 Stirling 近似，以对数计算避免数值溢出。

把复杂度与具体算法对应起来

算法	时间	辅助空间	理解重点
冒泡排序 ↗	$O(n^2)$	$O(1)$	辅助空间不含输入副本，详见课程
插入排序 ↗	$O(n^2)$	$O(1)$	辅助空间不含输入副本，详见课程
归并排序 ↗	$O(n\log n)$	$O(n)$	辅助空间不含输入副本，详见课程
快速排序 ↗	$O(n\log n)$	$O(\log n)$	平均情况；最坏 O(n²) 时间 / O(n) 栈
二分查找 ↗	$O(\log n)$	$O(1)$	有序数组
滑动窗口 ↗	$O(n)$	$O(\min(n, \|\Sigma\|))$	连续子数组 / 子串
广度优先搜索 ↗	$O(V+E)$	$O(V)$	无权图最短路
深度优先搜索 ↗	$O(V+E)$	$O(V+E)$	本课弹出时判重，栈可能重复
Dijkstra 最短路 ↗	$O(V^2+E)$	$O(V)$	线性选择最小距离的版本
单调栈 ↗	$O(n)$	$O(n)$	下一个更大元素
堆与优先队列 ↗	$O(n)$	$O(1)$	这里展示自底向上建堆成本
并查集 ↗	$O((V+E)\alpha(V))$	$O(V)$	动态加边
动态规划入门 ↗	$O(n)$	$O(n)$	计数 / 最优值