我有以下代码,我试图了解它的时间复杂度:
for (int i = 1 ; i <= n ; i = i*2)
for (int j = 1 ; j <= n ; j = j*2)
for (int k = 1 ; k <= j ; k++)
我做的是: 第一个循环运行log n次,第二个循环运行log n次,第三个循环是几何系列
总的来说,我的运行时间将是:n*(log(n))^2
它是否正确? 谢谢!
根据理论,你是正确的,复杂性是n*(log(n))^2
。
对于实际让我们迭代n = 1000:
i = 1; n= 1000; j= 1;k =1; result = 0
while i<=n:
j=1
while j<=n:
k=1
while k<=j:
result = result+1
k = k+1
j = j*2
i = i*2
print(result)
我们得到结果= 10230
所以我们使用floor(logn)+1) * (2 ^ floor(logn)+1) - 1)
公式得到的结果的实际值。对于n = 1000,它是10 *(2 ^ 10-1)
对于n = 2 ^ 25,我们得到结果1744830438,其也满足使用公式= 26 *((2 ^ 26)-1)= 1744830438。