时间与空间复杂度分析 - NOI提高级教程

📖 复杂度理论与大 O 表示法

在算法分析中，我们主要关注随着输入数据规模 $N$ 的增长，算法执行时间的增长趋势（Scale-up behavior）。我们使用 大 O 表示法（Big O Notation） 来忽略低阶项和常数系数，刻画出渐进时间与空间的上界。

在信息学奥赛中，评测机 1 秒钟通常能够执行约 $10^8$ 次基础指令操作。

拖动下方滑块调节数据规模 $N$。观察坐标系中各复杂度曲线的剧烈分化趋势，以及运算耗时计算器上的估算值。

数据规模 N：

CPU 每秒运行上限：

📈 增长速率几何曲线剖析 (X ∈ [0, 50])

⚠️ 若数据规模 N = 16，在大 O 视角下，各复杂度算法所需的理论操作步数和时间如下所示：

⏱️ 考场步数与物理耗时换算器

O(1) 常数级别 1 次 0.01 微秒

O(log N) 对数级别 4 次 0.04 微秒

O(N) 线性级别 16 次 0.16 微秒

O(N log N) 线性对数 64 次 0.64 微秒

O(N²) 平方级别 256 次 2.56 微秒

O(2ᴺ) 指数级爆炸 65,536 次 0.65 毫秒

💻 算法模板 C++ 实录对照

O(1) O(log N) O(N) O(N log N) O(N²) O(2ᴺ)

// O(1) 示例：常数级访问
int getElement(int a[], int index) {
    return a[index]; // 无论数组多大，哈希或数组下标寻址均为一步到位
}

🎬 指令执行流微观运行动态模拟

选择复杂度并点击"启动模拟"观察 CPU 循环执行轨迹

Operations: 0

空间复杂度描述算法执行过程中额外占用的最大物理内存空间。主要分为运行栈深度（递归开销）与堆区存储空间（动态内存分配）。

💾 运行栈 (Call Stack) 与堆内存开销可视化

当前运行递归栈 (Call Stack Frames - Max Stack Depth)

调用栈为空

动态分配堆内存 (Heap Space Allocation)

🧠 NOI 考点：递归栈空间深度解析

许多选手有一个极大的认知误区：认为指数级时间复杂度 $O(2^N)$ 的算法，其空间开销也是指数级的。这是完全错误的！

执行 fib(n) 时，虽然递归调用树包含多达 $2^N - 1$ 个节点（时间 $O(2^N)$），但递归在同一时刻只沿着某一条单路径向下探寻到底。

一旦叶子节点返回，该帧立即被弹出栈。因此系统栈的最大深度（空间复杂度）仅仅等于树的最大高度，即 $O(N)$ 级别！

📊 图与树的物理空间开销对比