c - 嵌套for循环的时间复杂度

Question

以下代码块 void function(int n) 的时间复杂度是多少。

我的尝试是最外面的循环将运行 n/2 次，而内部的两个循环将运行 2^q 次。然后我将 2^q 与 n 相等，得到 q 为 1/2(log n) 以 2 为底。乘以时间复杂度，我得到我的值 O(nlog(n)) 而答案是 O(nlog^2(n ））。

void function(int n) { 
    int count = 0; 
    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 
} 

标签： calgorithmtimetime-complexitybig-o

Answer 1

是时候应用理解循环嵌套的黄金法则了：

如有疑问，请由内而外！

让我们从原始的循环嵌套开始：

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2) 
                count++; 

该内部循环将运行 Θ(log n) 次，因为在循环的 m 次迭代之后，我们看到 k = 2 ^{m并且我们在 k ≥ n = 2 lg n}时停止。所以让我们用这个更简单的表达式替换那个内部循环：

    for (int i=n/2; i<=n; i++)  
        for (int j=1; j<=n; j = 2 * j)
            do Theta(log n) work;

现在，看看最里面的剩余循环。使用与之前完全相同的推理，我们看到这个循环也运行了 Θ(log n) 次。由于我们进行了 Θ(log n) 迭代，每个迭代都进行 Θ(log n) 工作，我们看到这个循环可以用这个更简单的循环代替：

    for (int i=n/2; i<=n; i++)
        do Theta(log^2 n) work;

在这里，外循环运行了 Θ(n) 次，所以总运行时间是 Θ(n log ² n)。

我认为，根据您在问题中所说的话，您有正确的见解，但只是忘记将对数项的两个副本相乘，一个用于两个内部循环中的每一个。