嵌套循环的 T(n)，我得到的答案是 (logn+1)(logn+2)，我是对的

Question

i=n;
while(i>=1){
    j=i;  
    while(j<=n){ 
        thetha(1)
        j=j*2;
    }
    i=i/2;
}

编辑 ：由于下面的op评论，更改了代码。

Answer 1

是的，您是正确的，因为外部循环是 Log(n(，内部循环是 Log(n(，它产生 (log n((log n(。

Log(n( 复杂度的原因是，循环中剩余的迭代次数在每次迭代时减半。这是通过将迭代变量i除以 2 还是通过将变量 j 乘以 2 来实现的无关紧要。完成循环所需的时间将为每个循环的 Log(n( 增长。

(log n

((log n( 的乘法是由于外部循环的每次迭代都会执行内部循环的 Log(n( 迭代。

添加是不必要的，因为在 big-O 表示法中，我们只关心一个函数相对于另一个函数的增长速率。用一个常数(或乘以一个常量(来抵消它不会改变函数的相对复杂度，所以最终结果是(log n((log n(。

Answer 2

在while(i>=1){ (...) }循环中，i大于 1(除了最后一次迭代外，明显更大(。因此，在 j=i 之后，j大于 1(除了最后一次迭代外，明显更大(。

因此，您的代码或多或少等同于：

i=n;
while(i>1){
    i=i/2;
}
if (i==1){
    j=i
    while(j<=1){ 
        thetha(1)
        j=j*2;
    }
}

可以重写：

i=n;
while(i>1){
    i=i/2;
}
if (i==1){
    thetha(1)
}

总体复杂性是 while 循环的复杂性，即 log(n(。