算法复杂度分析 - 频率计数法详解

一、什么是频率计数法？

频率计数法（Frequency Count Method） 是一种通过分析算法中每条语句的执行次数来计算时间复杂度的方法。

核心思想

1. 每条语句执行时间为 1 个单位
2. 统计每条语句的执行频率
3. 累加得到总时间函数 f(n)
4. 取最高次项 得到时间复杂度

关键点：我们关注的是增长趋势，而不是具体的执行时间。

二、频率计数法的基本规则

2.1 基本语句

语句 A;

• 执行次数：1 次
• 时间：1 个单位

2.2 循环语句

for (i = 0; i < n; i++) {
    语句;
}

执行次数分析：

• 初始化 i = 0：1 次
• 条件判断 i < n：n + 1 次（n 次为真，1 次为假）
• 自增 i++：n 次
• 循环体：n 次

总时间：f(n) = 1 + (n + 1) + n + n = 3n + 2

简化：通常只关注循环体，记为 O(n)

2.3 嵌套循环

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        语句;
    }
}

执行次数分析：

• 外层循环：n 次
• 内层循环：每次外层执行 n 次，共 n × n = n² 次
• 循环体：n² 次

总时间：O(n²)

三、实例分析

3.1 实例 1：数组求和

算法代码

int sum(int arr[], int n) {
    int s = 0;              // 语句 1
    for (int i = 0; i < n; i++) {  // 语句 2
        s = s + arr[i];    // 语句 3
    }
    return s;               // 语句 4
}

频率计数分析

时间复杂度

• 时间函数：f(n) = 3n + 4
• 最高次项：n（一次多项式）
• 时间复杂度：O(n)

空间复杂度

• 空间函数：S(n) = 4
• 空间复杂度：O(1)

注意：虽然数组本身占用 O(n) 空间，但在算法分析中，我们通常只计算额外空间，不包括输入数据。

3.2 实例 2：矩阵加法

算法代码

void matrixAdd(int A[][n], int B[][n], int C[][n], int n) {
    for (int i = 0; i < n; i++) {           // 语句 1
        for (int j = 0; j < n; j++) {       // 语句 2
            C[i][j] = A[i][j] + B[i][j];    // 语句 3
        }
    }
}

频率计数分析

时间复杂度

• 时间函数：f(n) = 3n² + 3n + 2
• 最高次项：n²（二次多项式）
• 时间复杂度：O(n²)

空间复杂度

• 空间函数：S(n) = 3n² + 3
• 空间复杂度：O(n²)

结论：矩阵加法的时间复杂度和空间复杂度都是 O(n²)

3.3 实例 3：矩阵乘法

算法代码

void matrixMultiply(int A[][n], int B[][n], int C[][n], int n) {
    for (int i = 0; i < n; i++) {           // 外层循环 1
        for (int j = 0; j < n; j++) {       // 外层循环 2
            C[i][j] = 0;                    // 语句 1
            for (int k = 0; k < n; k++) {   // 内层循环
                C[i][j] = C[i][j] + A[i][k] * B[k][j];  // 语句 2
            }
        }
    }
}

频率计数分析

时间复杂度

• 时间函数：f(n) = 3n³ + 6n² + 3n + 2
• 最高次项：n³（三次多项式）
• 时间复杂度：O(n³)

空间复杂度

• 空间函数：S(n) = 3n² + 3
• 空间复杂度：O(n²)

结论：矩阵乘法的时间复杂度是 O(n³)，空间复杂度是 O(n²)

三、实例分析（续）

3.4 实例 4：while 循环分析

算法代码

int i = 0;
while (i < n) {
    i = i + 1;
}

频率计数分析

时间复杂度

• 时间函数：f(n) = 2n + 2
• 最高次项：n（一次多项式）
• 时间复杂度：O(n)

说明：这个 while 循环等价于 for (i = 0; i < n; i++)，时间复杂度相同。

3.5 实例 5：对数增长 while 循环

算法代码

int a = 1;
while (a < n) {
    a = a * 2;
}

频率计数分析

执行过程追踪：

• 第 0 次：a = 1 = 2⁰
• 第 1 次：a = 2 = 2¹
• 第 2 次：a = 4 = 2²
• 第 3 次：a = 8 = 2³
• ...
• 第 k 次：a = 2ᵏ

循环终止条件：a >= n，即 2ᵏ >= n

求解 k：

2ᵏ = n
k = log₂(n)

时间复杂度

• 执行次数：log₂(n)
• 时间复杂度：O(log n)

关键点：当循环变量每次乘以常数（2、3、4...）时，循环次数为 O(log n)。

3.6 实例 6：递减型对数循环

算法代码

int i = n;
while (i > 1) {
    i = i / 2;
}

频率计数分析

执行过程追踪：

• 第 0 次：i = n
• 第 1 次：i = n/2
• 第 2 次：i = n/4 = n/2²
• 第 3 次：i = n/8 = n/2³
• ...
• 第 k 次：i = n/2ᵏ

循环终止条件：i <= 1，即 n/2ᵏ <= 1

求解 k：

n/2ᵏ <= 1
n <= 2ᵏ
2ᵏ >= n
k >= log₂(n)

时间复杂度

• 执行次数：log₂(n)
• 时间复杂度：O(log n)

规律：无论是"不断乘以常数"还是"不断除以常数"，时间复杂度都是 O(log n)。

3.7 实例 7：平方根复杂度循环

算法代码

int k = 1, i = 1;
while (k < n) {
    k = k + i;
    i = i + 1;
}

频率计数分析

执行过程追踪：

• 第 0 次：k = 1, i = 1
• 第 1 次：k = 1 + 1 = 2, i = 2
• 第 2 次：k = 2 + 2 = 4, i = 3
• 第 3 次：k = 4 + 3 = 7, i = 4
• 第 4 次：k = 7 + 4 = 11, i = 5
• ...
• 第 m 次：k = 1 + 2 + 3 + ... + m = m(m+1)/2

循环终止条件：k >= n，即 m(m+1)/2 >= n

求解 m：

m(m+1)/2 ≈ n  （当 m 较大时，m+1 ≈ m）
m²/2 ≈ n
m² ≈ 2n
m ≈ √(2n) ≈ √n

时间复杂度

• 执行次数：√n
• 时间复杂度：O(√n)

关键点：当循环变量以递增的步长累加时，执行次数为 O(√n)。

3.8 实例 8：GCD 算法（最大公约数）

算法代码

while (m != n) {
    if (m > n) {
        m = m - n;
    } else {
        n = n - m;
    }
}

频率计数分析

执行过程追踪（以 m=16, n=2 为例）：

• 第 1 次：m = 16 - 2 = 14, n = 2
• 第 2 次：m = 14 - 2 = 12, n = 2
• 第 3 次：m = 12 - 2 = 10, n = 2
• 第 4 次：m = 10 - 2 = 8, n = 2
• 第 5 次：m = 8 - 2 = 6, n = 2
• 第 6 次：m = 6 - 2 = 4, n = 2
• 第 7 次：m = 4 - 2 = 2, n = 2（相等，停止）

执行次数：16/2 = 8 次（实际 7 次，因为最后一次判断相等时不执行）

最好情况与最坏情况

时间复杂度

• 最好时间复杂度：O(1)
• 最坏时间复杂度：O(n)
• 平均时间复杂度：O(n)

说明：对于 while 循环，特别是条件复杂的循环，需要分析最好、最坏、平均三种情况。

3.9 实例 9：条件语句的时间复杂度

算法代码

if (n < 5) {
    print(n);
} else {
    for (int i = 0; i < n; i++) {
        // 执行 n 次
    }
}

频率计数分析

最好情况（n < 5）：

• 执行次数：1 次
• 时间复杂度：O(1)

最坏情况（n >= 5）：

• 执行次数：n 次
• 时间复杂度：O(n)

时间复杂度

• 最好时间复杂度：O(1)
• 最坏时间复杂度：O(n)

关键点：条件语句的时间复杂度取决于条件的真假，需要分别分析最好和最坏情况。

四、频率计数法总结

4.1 常见循环的时间复杂度

4.2 while 循环分析要点

while 循环与 for 循环的区别：

• for 循环的循环次数通常是已知的（如 n 次）
• while 循环的循环次数取决于条件，需要分析

while 循环分析步骤：

1. 追踪变量变化：写出每次迭代后变量的值
2. 找出终止条件：确定循环何时停止
3. 建立方程：根据终止条件建立数学方程
4. 求解迭代次数：解方程得到迭代次数 k
5. 得到时间复杂度：用大 O 表示法表示

典型 while 循环模式：

// 模式 1：对数增长
int a = 1;
while (a < n) {
    a = a * 2;  // 每次乘以常数
}
// 时间复杂度：O(log n)

// 模式 2：对数递减
int i = n;
while (i > 1) {
    i = i / 2;  // 每次除以常数
}
// 时间复杂度：O(log n)

// 模式 3：平方根复杂度
int k = 1, i = 1;
while (k < n) {
    k = k + i;  // 累加递增的步长
    i = i + 1;
}
// 时间复杂度：O(√n)

4.3 条件语句的时间复杂度

条件语句的特点：

• 条件为真和为假时执行不同的代码路径
• 需要分别分析最好情况和最坏情况

分析示例：

if (n < 5) {
    print(n);  // O(1)
} else {
    for (int i = 0; i < n; i++) {
        // O(n)
    }
}

注意：对于条件语句，通常报告最坏时间复杂度，因为它提供了性能的上限保证。

4.4 计算步骤

1. 识别基本语句：找出算法中的核心操作
2. 统计执行次数：分析每条语句的执行频率
3. 累加时间函数：f(n) = Σ(执行次数 × 单位时间)
4. 取最高次项：忽略低次项和常数系数
5. 得到复杂度：用大 O 表示法表示

4.5 简化规则

• 忽略常数项：f(n) = n² + 5n + 3 → O(n²)
• 忽略系数：f(n) = 3n² + 2n → O(n²)
• 只保留最高次项：关注增长趋势

4.2 计算步骤

1. 识别基本语句：找出算法中的核心操作
2. 统计执行次数：分析每条语句的执行频率
3. 累加时间函数：f(n) = Σ(执行次数 × 单位时间)
4. 取最高次项：忽略低次项和常数系数
5. 得到复杂度：用大 O 表示法表示

4.3 简化规则

• 忽略常数项：f(n) = n² + 5n + 3 → O(n²)
• 忽略系数：f(n) = 3n² + 2n → O(n²)
• 只保留最高次项：关注增长趋势

五、实践技巧

5.1 快速估算方法

// 单层循环 → O(n)
for (int i = 0; i < n; i++) {
    // O(1) 操作
}

// 双层循环 → O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) 操作
    }
}

// 三层循环 → O(n³)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // O(1) 操作
        }
    }
}

5.2 特殊情况

5.2.1 条件循环

for (int i = 1; i < n; i *= 2) {  // i = 1, 2, 4, 8, ...
    // 执行 log₂(n) 次
}

设循环执行了 k 次，则第 k 次迭代后：

i = 2^k;

循环终止条件是 i >= n，因此有：

2^k >= n;

两边同时取以 2 为底的对数，可得：

k >= log2(n);

所以该循环的执行次数是 log 级别，时间复杂度为：

• 时间复杂度：O(log n)

规律：如果循环变量不是每次加 1，而是每次乘以 2、3、4... 这样的常数，那么循环次数通常是 O(log n)。

5.2.2 log n 为什么有时要取上整？

当 n 恰好是 2 的幂时，log₂n 是整数；但当 n 不是 2 的幂时，执行次数通常要写成：

ceil(log2(n))

也就是 向上取整。

例如：

• n = 8 时，循环序列是 1 -> 2 -> 4，共执行 3 次，而 log₂8 = 3
• n = 10 时，循环序列是 1 -> 2 -> 4 -> 8，共执行 4 次，而 log₂10 ≈ 3.32

因此更精确地说：

for (int i = 1; i < n; i *= 2) {
    // statement
}

执行次数约为 ⌈log₂n⌉，但在大 O 表示法中仍然统一记为 O(log n)。

5.2.3 递减型对数循环

除了“不断乘以 2”的写法，还有另一种常见形式：

for (int i = n; i >= 1; i /= 2) {
    // statement
}

设循环执行了 k 次，则：

i = n / 2^k;

循环结束时有：

n / 2^k < 1;

整理得到：

2^k > n;

因此：

k = O(log n);

也就是说：

• 不断乘一个常数，通常得到 O(log n)
• 不断除一个常数，通常也得到 O(log n)

5.2.4 平方根循环

有些循环虽然是按 1 递增，但循环条件不是 i < n，而是 i * i <= n：

for (int i = 1; i * i <= n; i++) {
    // statement
}

当循环停止时，满足：

i * i > n;

因此临界点在：

i ≈ sqrt(n);

所以该循环的时间复杂度为：

• 时间复杂度：O(√n)

5.2.5 部分循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {  // j 从 0 到 i-1
        // 执行次数：1 + 2 + 3 + ... + (n-1) = n(n-1)/2
    }
}

• 时间复杂度：O(n²)

5.3 独立循环与嵌套循环

这是初学者最容易混淆的地方。

5.3.1 两个独立循环：时间相加

for (int i = 0; i < n; i++) {
    // O(1)
}

for (int j = 0; j < n; j++) {
    // O(1)
}

这两个循环是前后顺序执行，不是嵌套关系。

• 第一个循环：O(n)
• 第二个循环：O(n)
• 总时间：O(n + n) = O(2n) = O(n)

结论：独立循环的时间复杂度是相加，不是相乘。

5.3.2 嵌套循环：时间相乘

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        // O(1)
    }
}

• 外层循环执行 n 次
• 内层循环执行 log n 次

因此总时间为：

n * log n = O(n log n);

5.4 log log n 的典型例子

如果一个变量本身是通过对数循环得到的，再把它作为另一个对数循环的上界，就会出现 log log n。

int p = 0;

for (int i = 1; i < n; i *= 2) {
    p++;
}

for (int j = 1; j < p; j *= 2) {
    // O(1)
}

分析如下：

• 第一段循环执行 O(log n) 次，因此 p = O(log n)
• 第二段循环的上界变成了 p
• 所以第二段循环的时间复杂度是 O(log p)

代入 p = log n：

O(log p) = O(log(log n));

即：

• 时间复杂度：O(log log n)

5.5 常见循环模式速查

下面这些形式可以直接作为经验公式来记：

补充说明：

• n / 2、n / 10、100n 在大 O 表示法中都记为 O(n)
• log₂n、log₃n、log₁₀n 在大 O 表示法中都记为 O(log n)
• 我们保留的是增长趋势，不保留常数系数与对数底数

六、时间复杂度分类

6.1 时间复杂度的分类依据

时间复杂度根据算法执行时间随输入规模 n 的增长趋势进行分类，帮助我们理解算法的效率。

6.2 各类时间复杂度详解

6.2.1 常数时间复杂度 O(1)

定义：执行时间不依赖于输入规模 n。

特点：

• 无论输入多大，执行时间都是固定的
• 包括常数如 2、5、5000 等，只要与 n 无关都记为 O(1)

示例：

int arr[100];
int value = arr[50];  // 无论数组多大，访问第 50 个元素的时间相同

6.2.2 对数时间复杂度 O(log n)

定义：执行时间随输入规模呈对数增长。

特点：

• 底数不影响分类（log₂n、log₃n、log₁₀n 都记为 O(log n)）
• 增长非常缓慢，效率很高

示例：

// 二分查找
while (left <= right) {
    mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

6.2.3 线性时间复杂度 O(n)

定义：执行时间随输入规模线性增长。

特点：

• 函数形式如 f(n) = 2n + 3、f(n) = 500n + 700、f(n) = n/5000 + 6
• 都被 n 项主导，记为 O(n)

示例：

// 遍历数组
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

6.2.4 多项式时间复杂度

二次复杂度 O(n²)：

// 双重循环
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        arr[i][j] = i + j;
    }
}

三次复杂度 O(n³)：

// 三重循环（如矩阵乘法）
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

6.2.5 指数时间复杂度 O(2ⁿ)

定义：执行时间随输入规模呈指数级增长。

特点：

• 包括 O(2ⁿ)、O(3ⁿ)、O(nⁿ) 等形式
• 增长极快，仅适用于小规模输入
• 通常出现在递归算法或暴力搜索中

示例：

// 斐波那契数列（递归实现）
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 时间复杂度 O(2ⁿ)
}

6.3 函数增长阶序

函数按增长速率从小到大排列：

$\log n < n < n^2 < n^3 < \cdots < n^{100} < 2^n < n!$

具体数值对比：

观察：

• 当 n 较小时，某些函数可能看起来增长相近
• 但随着 n 增大，指数函数会远远超过多项式函数
• 即使 n¹⁰⁰ 在 n 较小时可能大于 2ⁿ，但最终 2ⁿ 会超越

6.4 增长速率的动态特性

重要理解：

1. 初始阶段：某些高阶函数可能看起来与低阶函数相近
2. 长期趋势：对于足够大的 n，高阶函数必然超过低阶函数
3. 临界点：不同函数之间存在交叉点，但顺序不变

示例：

• n² 与 2ⁿ 在 n=2 和 n=4 时相等
• 但当 n > 4 后，2ⁿ 始终大于 n²
• 对于任意多项式 nᵏ 和指数函数 aⁿ（a > 1），当 n 足够大时，aⁿ > nᵏ

6.5 图形化理解

如果将这些函数绘制成图：

• log n：曲线平缓上升
• n：直线上升
• n²：抛物线，上升越来越快
• n³：更陡峭的曲线
• 2ⁿ：几乎垂直上升

启示：选择算法时，应优先考虑低阶时间复杂度的算法。

6.6 时间复杂度分类总结表

七、总结

7.1 核心要点

1. 频率计数法通过统计语句执行次数来分析时间复杂度
2. 每条语句执行时间为 1 个单位
3. 循环执行次数 = 循环条件 × 循环体
4. 嵌套循环执行次数 = 各层循环次数相乘
5. 独立循环执行次数相加，嵌套循环执行次数相乘
6. 变量按倍数增长或缩小时，循环次数通常是 O(log n)
7. 时间复杂度取时间函数的最高次项
8. while 循环需要追踪变量变化，分析终止条件
9. 条件语句需要分别分析最好和最坏情况

7.2 时间复杂度分类要点

1. O(1)：执行时间与输入规模无关
2. O(log n)：增长极慢，效率很高
3. O(n)：线性增长，常见于单次遍历
4. O(n²)：二次增长，常见于双重循环
5. O(n³)：三次增长，常见于三重循环或矩阵运算
6. O(2ⁿ)：指数增长，仅适用于小规模输入

7.3 实例对比

7.4 下一步学习

掌握了频率计数法后，你可以继续学习：

• 大 O 表示法的严格定义
• 最好、最坏、平均情况分析
• 递归算法的复杂度分析
• 空间复杂度的深入分析

记住：频率计数法是算法分析的基础工具，熟练掌握它对于理解算法效率至关重要！

附录：while 循环分析速查表

提示：对于 while 循环，关键是追踪变量变化并找出终止条件。

参考资料

• 《算法导论》（Introduction to Algorithms）
• 《计算机算法设计与分析》
• LeetCode 算法题库

本文根据视频讲座内容整理，适合算法初学者阅读。