c++ - 尝试计算算法的运行时间

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，第二个循环通过 2 的幂运行 j，直到它超过 n:1, 2, 4, 8 , ... , 2^h，其中 h=int(log₂n)。所以最内层循环的主体运行 2⁰ + 2¹ + ... + 2^h = 2^{h+ 1}-1次。并且 2^h+1-1 = 2^{int(log₂n)+1}-1 这是 O(n)。

现在，外层循环执行了 n 次。这使得整个事情的复杂度为 O(n*n)。