试图计算算法的运行时间

Question

我有以下算法:

for(int i = n; i > 0; i--){
    for(int j = 1; j < n; j *= 2){
        for(int k = 0; k < j; k++){
            ... // constant number C of operations
        }
    }
}

我需要计算算法的运行时间复杂度,

我很确定外循环运行O(n)时间,中间循环运行O(log(n))时间,内循环运行O(log(n))时间,但我不太确定它.

运行时间复杂性的最终结果是O(n^2),但我不知道如何.

希望有人可以给我一个简短的解释,谢谢!

Answer 1

对于每个i,第二个循环j遍历2的幂,直到它超过n:1,2,4,8,...,2 ^h,其中h = int(log ₂ n).因此,最内部循环的主体运行2 ⁰ + 2 ¹ + ... + 2 ^h = 2 ^{h + 1} -1次.并且^{2h + 1} -1 = 2 ^{int(log ₂ n)+1} -1,即O(n).

现在,外循环执行n时间.这给出了整个事物O(n*n)的复杂性.