关于嵌套循环代码渐近上界运行时间是否为O(n²)的问询

先看你提供的代码：

while (j < n2) { // executes n2-1 times
    int k = 0;
    while ((k < n1) && (seq[k] < seq2[j])) { // executes (n2-1)*n1 times
        k = k + 1;
    }
    // we want to insert seq2[j] at seq[k]
    // so we move seq[k] through seq[n1 - 1] to the right
    for (int i = n1; i > k; i = i - 1) { // some n-k times
        seq[i] = seq[i - 1];
    }
    seq[k] = seq2[j];
    j = j + 1;
    n1 = n1 + 1;
}

直接给结论：是的，这个算法的最坏情况运行时间确实是$O(n^2)$，下面我们一步步拆解验证：

1. 外层主循环的迭代次数 #

外层while (j < n2)每次迭代后j自增1，所以总共会执行n2次（注释里写n2-1次，应该是初始j从1开始，但渐近复杂度里常数项可以忽略）。另外每次迭代后n1会加1，所以n1会从初始值（假设为m）逐步增长到m + n2 - 1。

2. 内层while循环的最坏情况开销 #

内层的while ((k < n1) && (seq[k] < seq2[j]))，最坏情况是每次seq2[j]都比当前seq数组里的所有元素都大。这时候k会从0一直遍历到n1，也就是每次迭代执行n1次判断和递增操作。

把所有主循环迭代的次数加起来，总次数是一个等差数列求和：
m + (m+1) + (m+2) + ... + (m + n2 - 1)
计算结果为n2*m + n2*(n2-1)/2。如果我们假设初始的n1和n2是同量级的（比如两个输入数组长度都是n，即m = O(n)，n2 = O(n)），那么这个和的渐近量级就是O(n^2)。

3. 内层for循环的最坏情况开销 #

再看移动元素的for循环，最坏情况是每次插入位置k=0（也就是seq2[j]比seq里所有元素都小），这时候需要把seq里的所有元素都向右移动一位，执行次数等于当前的n1次。

同样把所有主循环迭代的次数加起来，总次数和上面的while循环完全一致，也是O(n^2)。

4. 总时间复杂度 #

把所有部分的开销加起来：主循环的常数操作（可忽略） + while循环的O(n^2) + for循环的O(n^2)，总的渐近上界就是O(n^2)。

哪怕初始n1是很小的常数（比如1），n2是n，总次数也是1+2+...+n = n(n+1)/2 = O(n^2)，依然是平方级复杂度。

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