如何以大Θ符号分析算法运行时间？嵌套循环复杂度分析求助

下面是我平时分析算法复杂度时的实操步骤，都是经过验证的实用方法：

• 第一步：锁定核心基本操作
  先找到算法中执行次数最多、对耗时影响最大的操作，比如数组元素的比较、赋值，或者递归调用里的核心计算步骤。那些只执行几次的初始化、收尾操作不用纠结，它们对复杂度的阶数没有影响。

• 第二步：统计执行次数，写出T(n)
  把这个基本操作的总执行次数表示成输入规模n的函数，记为T(n)。如果算法在不同输入下执行次数差异很大，可能需要分别分析最好、最坏、平均情况，但大Θ描述的是紧界——也就是当n足够大时，T(n)的增长速度被某个函数g(n)上下夹住。

• 第三步：简化T(n)，去掉无关项
  忽略T(n)中的低阶项和常数系数，比如T(n)=4n³+10n²+5，直接简化成n³就行。因为当n趋近于无穷大时，低阶项（比如n²）和常数的影响会被最高阶项完全覆盖。

• 第四步：验证大Θ的紧界条件
  找到一个函数g(n)，确保存在两个正常数c₁、c₂和一个阈值n₀，当n≥n₀时，满足c₁*g(n) ≤ T(n) ≤ c₂*g(n)。只要这个条件成立，就可以说T(n) = Θ(g(n))——简单来说，就是T(n)和g(n)的增长速度完全一致。

• 第五步：交叉验证
  确认你找到的g(n)同时满足大O（上界）和大Ω（下界）的条件，不能只满足其中一个，毕竟大Θ是两者的交集。

首先直接给结论：绝对不能直接用「外层循环复杂度×内层循环复杂度」来粗暴判断，因为内层while循环的执行次数明显依赖外层for循环的变量，这种情况下必须拆解分析，累加每次外层迭代时内层的执行次数。

举两个常见的例子帮你理解：

例子1：线性递减的内层次数 #

for (int i = 0; i < n; i++) {
    int j = i;
    while (j < n) {
        // 假设这里是核心基本操作
        j++;
    }
}

外层循环i从0到n-1，第i次外层迭代时，内层while会执行n - i次。总执行次数就是：
n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
简化后就是Θ(n²)——这时候虽然外层是n次，但内层每次次数递减，累加后还是平方阶。

例子2：指数增长的外层变量 #

for (int i = 1; i < n; i *= 2) {
    int j = 0;
    while (j < i) {
        // 核心基本操作
        j++;
    }
}

外层循环的i是1、2、4、8…直到小于n，总共迭代log₂n次。但每次内层的执行次数是i次，总次数是1 + 2 + 4 + ... + 2^k（其中2^k <n），这个求和结果是2^(k+1)-1，而2^(k+1)约等于n，所以总次数是Θ(n)——如果粗暴用外层的logn乘内层的n，结果就完全错了。

至于分析过程的复杂度：其实真没你想的那么复杂，核心就是两步：

1. 写出每次外层迭代时，内层while循环的执行次数表达式；
2. 把所有外层迭代的内层次数加起来，得到总次数的求和式，再用大Θ的规则简化这个求和式的阶数。

遇到这种情况别慌，这是算法复杂度分析里的常见场景，只要一步步拆解求和，就能得到正确的结果。

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