这些循环的时间复杂度函数 [ T(n) ] 是多少？

Question

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

我的目标是找到 T(n)（为我们提供算法执行次数的函数），其顺序预计为 n.log(n)，但我需要至少对 n 可以正常工作的确切函数=1 到 n=10 数据

我尝试预测函数，最后我以 *T(n) = floor((n-1) log(n)) + n

这仅适用于 n=1 和 n=2。

我应该提一下，我发现通过将原始代码转换为 for 循环的函数不准确，如下所示：

for ( j = 1 ; j <= n ; j*= 2) {
    for ( i = j ; i<= n ;  i*=2 ) {
        cout << "Printed";
    }
}

最后，感谢您帮助我提前找到准确的 T(n)。

Answer 1

外循环和内循环都是O(log₂ N).

所以总时间是

O(log₁₀ N * log₂ N) == O(2 * log₂ N)

刚刚减少到 O(lg N)

Answer 2

使用log(x)是基于log的floor 2

1.) 内循环执行 1+log(N)-log(j) 外循环执行 1+log(N) 次，其中 j=1,2,4...N 次，总复杂度为 T(N)=log(N)log(N)+2*log(N)+1-(log(1)+log(2)+log(4)...+log(N))= log(N)^2-(0+1+2+...+log(N))+2*log(N)+1= log(N)^2-log(N)(log(N)-1)/2+1= log(N)^2/2+3*log(N)/2+1

2.) 此处相同，只是顺序相反。

我知道这不是证明，但可能比数学更容易理解：godbolt 玩 n。它总是 returns 0;

这些循环的时间复杂度函数 [ T(n) ] 是多少？

What's the time-complexity function [ T(n) ] for these loops?

c++

complexity-theory

for-loop

time-complexity

data-structures