每日科普 · 2026-10-04 周日

考研 408 × 求职面试

知识点 · 算法设计与分析 · 基础

常见函数的增长阶与复杂度量级比较

增长阶描述当输入规模 n 越来越大时，运行时间或空间开销随 n 增长的趋势，忽略常数系数和低阶项。
常见量级从小到大：O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)。
比较时可把两个函数相除看极限：若 f(n)/g(n) 趋于 0，则 f 比 g 低阶；趋于常数则同阶；趋于无穷则更高阶。
关键结论：log n 慢于任何正幂 n^ε；n log n 介于 n 与 n^2 之间；指数阶很快超过任意多项式。
注意 O 是上界，Ω 是下界，Θ 是紧确界。说“复杂度是 O(n^2)”不代表恰好 n^2，只表示不超过某个常数倍的 n^2。

每日一题 · 算法设计与分析

常见函数的增长阶与复杂度量级比较

下列复杂度关系正确的是？
A. n log n = O(n)
B. 2^n = O(n^2)
C. n^2 + 3n = Θ(n^2)
D. log n = Ω(n)

解析

C 正确。n^2+3n 的最高阶项是 n^2，常数系数和低阶项 3n 在渐近意义下可忽略，因此它与 n^2 同阶，是 Θ(n^2)。A 中 n log n 比 n 增长快，不是 O(n)；B 中指数 2^n 最终远快于多项式 n^2；D 中 log n 比 n 慢，不是 Ω(n)。

面试小贴士 · 算法设计与分析

常见函数的增长阶与复杂度量级比较

面试常问排序、查找算法的复杂度排序，或判断 O/Θ 是否成立。答题先假设 n 很大，只保留最高阶，再用相除看极限；易错点是把 log 底数当量级差别、把 n log n 说成 O(n)、忽略最坏/平均情况。

代码实现 · C

代码示例

#include <stdio.h>
#include <math.h>

int main() {
    int ns[] = {10, 100, 1000}; // 测试规模
    for (int i = 0; i < 3; i++) {
        int n = ns[i];
        double logn = log2(n); // 对数阶
        // 输出各函数随 n 的增长
        printf("n=%d: log2n=%.2f, n=%d, nlog2n=%.2f, n^2=%d\n",
               n, logn, n, n * logn, n * n);
    }
    return 0;
}