时间复杂度和几何系列,嵌套循环

问题描述 投票:1回答:1

我有以下代码,我试图了解它的时间复杂度:

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

它是否正确? 谢谢!

loops time-complexity big-o
1个回答
-1
投票

根据理论,你是正确的,复杂性是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。

© www.soinside.com 2019 - 2024. All rights reserved.