algorithm - 两个循环但 Theta(n)？

Question

i = n
while (i >= 1)
{
    for j = 1 to i 
    {
    Function() <- (O(1))
    }
i = i/2
}

答案是 Theta(n) 但我不明白为什么是 Theta(n)。

根据我的理解，内循环将执行 n + n/2 + n/4 +...+1 所以总数将为 O(n) 并且外循环将执行 logn 时间所以答案应该是 nlogn。但为什么这是 Theta(n) 而不是 Theta(nlogn)？

Answer 1

正如您正确指出的那样，内部循环将执行 n + n/2 + n/4 + ... + 1 ≈ 2*n 次。

让我们看看每行代码将被执行多少次。

i = n                  // Executed 1 time
while (i >= 1)         // Executed approximately log(n) times
{
    for j = 1 to i     // Executed approximately 2*n times
    {
        Function()     // Executed approximately 2*n times
    }
    i = i/2            // Executed approximately log(n) times
}

所以算法的总时间复杂度为:

Θ(1) + Θ(log(n)) + Θ(n) + Θ(n) + Θ(log(n))

等同于Θ(n)。