两个循环，但是Theta（n）？ [英] two loops but Theta(n)?

问题描述

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

答案是Theta（n），但我不明白为什么是Theta（n）。

The answer is Theta(n) but I do not understand why this is Theta(n).

根据我的理解，内部循环将执行n + n / 2 + n / 4 + ... + 1，因此总数将为O（n），外部循环将在登录时间执行，因此
的答案应为nlogn。
但是为什么这是Theta（n）而不是Theta（nlogn）？

From my understanding, the inner loop will execute n + n/2 + n/4 +...+1 so the total will be O(n) and the outer loop will be executed logn time so the answer should be nlogn. But why this is Theta(n) instead of Theta(nlogn)?

推荐答案

您的计算部分正确。您只是错过了一个很小的细节，而您已经在其中计算了外循环的复杂性。在您的情况下，您选择通过简单地计算外部循环中每个迭代所花费的时间来计算时间复杂度。那就是：

Your calculations are partially correct. You are simply missing out on a small detail in which you have already calculated the outer loop's complexity. In your case, you chose to calculate time complexity by simply calculating the time each iteration in the outer loop takes. And that is:

for i=n : O(n)

for i=n/2: O(n/2)

.
.
.

for i=1: O(1)

现在，计算结果根据内部循环的时间复杂度进行的每次迭代。因此，总的时间复杂度是外部循环所花费的时间（包括内部循环所花费的时间），它是运行每次迭代所花费的时间之和，即： n + n / 2 + n / 4 + ... + 1 。

Now, the calculations for each iteration where made based on the time complexity of the inner loop. Therefore, the total time complexity is how much the outer loop takes (which includes the time the inner loop takes) which is the sum of how much it takes to run each iteration which is: n+n/2+n/4+...+1.

您所指的乘法是一种当您知道外循环运行以及内循环运行多少次，然后将它们相乘即可得出总体时间复杂度。您也可以选择将内循环运行自身的次数增加n次，而n是外循环运行的次数（简单数学：k * n = k + k + ... + kn次）。

The multiplication you were referring to is a technique used when you know how many times the outer loop runs and how many times the inner loop runs and you multiply them to get the overall time complexity. You could have alternatively, added the number of times the inner loop runs to itself n times whereas n is the number of times the outer loop runs (simple mathematics: k*n = k+k+...+k n times).

因此，在您的情况下，您仅使用第二种方法，因为n + n / 2 + n / 4 + ... + 1的次数不是内部循环运行，它是在外部循环的每次迭代中运行多少次的总和。

So in your case, you're simply using the second method, since n+n/2+n/4+...+1 is not the number of times the inner loop runs, it's the sum of how many times it runs in each iteration of the outer loop.

这篇关于两个循环，但是Theta（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！