如何使用大O表示法计算嵌套循环算法的运行时间复杂度

待分析伪代码 #

Algorithm(N):
    int i = n;
    int j;
    new Array sum[(n + 1) / 2];
    while i > 1 do
        j = i;
        while j < n do
            for k = 0; k < n; k = k + 2 do
                sum[k / 2] = sum[(k / 2) - 1] + k;
            end
            j = j * 2;
        end
        i = i / 2;
    end 
    return sum

复杂度分层计算 #

我们从最内层循环向外逐层分析：

• 最内层k循环：k从0开始每次加2，直到达到n，总执行次数为n/2，时间复杂度为O(n)
• 中间层j循环：j初始值等于当前的i，每次乘2直到大于等于n，执行次数为log₂(n/i)，结合内层循环，单轮j循环的时间复杂度为O(n) × log₂(n/i)
• 最外层i循环：i初始值为n，每次除以2直到小于等于1，执行次数为log₂n次，i的取值依次为n、n/2、n/4……2

总复杂度推导 #

将三层循环的执行次数合并求和：
总操作次数 = （n/2） × [ log₂(n/n) + log₂(n/(n/2)) + log₂(n/(n/4)) + …… + log₂(n/2) ]
括号内的求和项为0+1+2+……+(log₂n -1)，求和结果为 (log₂n)(log₂n -1)/2，量级为O(log²n)
乘以最内层的n系数后，总时间复杂度为O(n log²n)
另外开头的数组初始化操作为O(n)，量级低于O(n log²n)，不影响最终复杂度结果。

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