嵌套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++; 
} 

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).

我认为,根据你在你的问题中所说的,你有正确的见解但只是忘了在两个副本的日志项中相乘,一个用于两个内循环中的每一个.