尝试计算算法的 运行 时间
Trying to calculate running time of an algorithm
我有以下算法:
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)
,但我不知道如何。
希望有人能给我一个简短的解释,谢谢!
对于每个 i
,第二个循环运行 j
2 的幂,直到它超过 n
:1, 2, 4, 8, ... , 2h,其中 h=int(log2n)。所以最内层循环的主体运行 20 + 21 + ... + 2h = 2h+1-1 次。和 2h+1-1 = 2int(log2n)+1-1 其中是 O(n).
现在,外循环执行了 n
次。这使整个事情变得复杂 O(n*n).
我有以下算法:
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)
,但我不知道如何。
希望有人能给我一个简短的解释,谢谢!
对于每个 i
,第二个循环运行 j
2 的幂,直到它超过 n
:1, 2, 4, 8, ... , 2h,其中 h=int(log2n)。所以最内层循环的主体运行 20 + 21 + ... + 2h = 2h+1-1 次。和 2h+1-1 = 2int(log2n)+1-1 其中是 O(n).
现在,外循环执行了 n
次。这使整个事情变得复杂 O(n*n).