GESP 八级 · GESP202609 C++ 八级 第 13 题

下列常见复杂度量级，按渐近增长速度从慢到快排列，正确的是（　　）。

看到题先想“渐近增长率”的固定阶梯：常数级 O(1) 最慢，接着对数级 O(log n)、线性级 O(n)、线性对数级 O(n log n)、平方级 O(n²)、指数级 O(2ⁿ)、阶乘级 O(n!) 最快。命题人把这几个量级打乱，考的是对阶乘与指数谁更快、对数与线性谁更慢的直觉。正确思路是先把 O(1) 放最前，再按 O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) 的顺序排，然后对照选项，排除把 O(2ⁿ) 排在 O(n²) 前面或把 O(log n) 排在 O(n) 后面的错误项。

选项 A 把 O(2ⁿ) 排在 O(n²) 前面，误以为指数级比平方级慢；选项 B 把 O(n) 排在 O(log n) 前面，混淆线性与对数增长；选项 D 把 O(n!) 排在 O(2ⁿ) 前面，忽略了阶乘爆炸式增长。最阴险的细节是“渐近”二字——它要求忽略常数系数和低阶项，只比最高阶的增长速度，很多考生会纠结于具体数值（如 2ⁿ 与 n² 在 n 较小时的大小），反而掉进陷阱。

1. 考纲定位

GESP 八级算法复杂度模块，命题人卡住的是“阶乘与指数谁更快”“对数与线性谁更慢”这两个经典误区。

2. 解题思维

先列出标准阶梯 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)，再逐项核对选项。C 项顺序与阶梯完全吻合，其他三项均存在越序。