如何计算给定C++双层循环代码的渐近复杂度f(n)并确定上下界

第一步：明确输入规模的定义 #

要推导通用运行步数函数，首先需要明确输入规模的约定，这段代码包含两个独立的维度参数rows和cols，通常有两种常见的定义方式：

• 单参数定义：适合两个参数同阶增长的场景（比如处理n阶方阵时rows=cols=n，或者令n = max(rows, cols)）
• 双参数定义：适合两个参数独立变化的场景

第二步：整合观测结果推导总运行步数f(n) #

我们先把所有操作的开销都视为常数量级（无论是循环的条件判断、变量自增还是内部statement执行，单次运行的耗时都和输入规模无关），结合你观测到的执行次数：

for(int i=0; i<rows; i++)
{
    for(int j=0; j<cols; j++)
    {
        statement;
    }
}

所有操作的总运行步数可以合并为：

• 如果用双参数表示：f(rows, cols) = a * rows * cols + b * rows + c，其中a、b、c都是和输入规模无关的正常数，分别对应内层循环相关操作的平均常数开销、外层循环控制的平均常数开销、初始赋值等固定开销
• 如果用单参数n = max(rows, cols)表示：f(n) = a * n² + b * n + c

第三步：确定复杂度上下界 #

根据渐近复杂度的定义，常数系数和低阶项都可以忽略：

• 上界（大O表示）：如果是单参数场景，f(n) = O(n²)；如果是双参数场景，f(rows, cols) = O(rows * cols)
• 下界（Ω表示）：只要rows和cols都不低于同阶的常数比例，单参数场景下f(n) = Ω(n²)，双参数场景下f(rows, cols) = Ω(rows * cols)
• 紧界（Θ表示）：上下界一致的前提下，单参数场景为Θ(n²)，双参数场景为Θ(rows * cols)

如果存在其中一个参数是常数的特殊场景（比如rows固定为10，只有cols随n增长），那低阶项就会变成主导项，此时复杂度会退化为O(n)，需要结合实际参数的变化规则判断。

内容的提问来源于stack exchange，提问作者Adam Saleem