每日科普 · 2026-09-26 周六

考研 408 × 求职面试

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

渐近记号：大 O、大 Ω 与大 Θ

渐近记号描述输入规模 n 增大时，算法运行时间或空间开销的增长趋势；它忽略常数、系数和低阶项，只关心数量级。
1. 大O：上界。f(n)=O(g(n)) 表示存在正常数 c、n0，当 n≥n0 时，0≤f(n)≤c·g(n)。例如 3n²+2n+1=O(n²)，也可写成 O(n³)，但后者更松。
2. 大Ω：下界。表示存在 c、n0，当 n≥n0 时，f(n)≥c·g(n)。例如 3n²+2n+1=Ω(n²)，说明增长至少是这个量级。
3. 大Θ：紧界。同时满足 O 和 Ω，即存在 c1、c2、n0，使 c1·g(n)≤f(n)≤c2·g(n)。例如 3n²+2n+1=Θ(n²)。
易错：O 不一定最紧；Ω 也不一定最紧；Θ 才表示与 g(n) 同阶。分析时抓最高阶项。

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

渐近记号：大 O、大 Ω 与大 Θ

设 f(n)=2n²+5n+7，下列关于其渐近界最准确的是？
A. f(n)=O(n)
B. f(n)=Ω(n³)
C. f(n)=Θ(n²)
D. f(n)=O(n³) 但 f(n)≠Ω(n²)

解析

最高阶项是 n²，低阶项和系数不影响渐近阶，因此 f(n)=Θ(n²)。A 说 O(n) 太小，因为 n² 增长更快；B 下界到 n³ 不成立；D 后半句错误，因为 f(n)=Ω(n²) 成立。故选 C。

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

渐近记号：大 O、大 Ω 与大 Θ

面试常问：O、Ω、Θ 区别；给代码求复杂度；问“最紧界”。答法：先定义上界/下界/紧界，再忽略常数低阶，强调最紧常用 Θ。易错：把 O 当精确复杂度，或忽略 n0。

代码实现 · C

代码示例

#include <stdio.h>

int main(void) {
    int n;
    for (n = 1; n <= 10; n++) {
        long f = 3L*n*n + 2L*n + 1; // f(n)
        long g = 1L*n*n;            // g(n)
        // 当 n 足够大时，3g <= f <= 4g，即 f=Θ(g)
        if (f >= 3*g && f <= 4*g)
            printf("n=%d, f=%ld, g=%ld, 满足 Θ 的常数夹逼\n", n, f, g);
        else
            printf("n=%d, f=%ld, g=%ld, 尚未夹逼\n", n, f, g);
    }
    return 0;
}