algorithm - Theta 表示法和最坏情况运行时间嵌套循环

Question

这是我需要分析的代码:

i = 1
while i < n
  do
    j = 0;
    while j <= i
       do
          j = j + 1
    i = 2i

所以，第一个循环应该运行 log(2,n)，最里面的循环应该运行 log(2,n) * (i + 1)，但我很确定这是错误的。我如何使用 theta 符号来证明它？

Answer 1

思考这个问题的一种直观方法是查看您的内部循环为外部循环变量i的固定值做了多少工作>。它显然与 i 本身一样多。因此，如果 i 的值为 256，那么您将执行 j = j + 1 多次。

因此，完成的总工作量是 i 在外循环执行中所采用的值的总和。该变量正在迅速增加以 catch n。它的值由 i = 2i 给出(应该是 i = 2*i)，将类似于:2, 4, 8, 16 , ...，因为当 i = 1 时，我们从内部循环的 2 次迭代开始。这是一个几何级数:a, ar, ar^2 ...，a = 1 和 r = 2。正如您所计算的，最后一项将是 n 并且该系列中将有 log2 n 项。这就是几何级数的简单求和。

对于这个算法来说，有最坏情况或最好情况没有多大意义，因为输入没有不同的排列，在这种情况下输入只是一个数字 n。当特定输入(例如特定的数字序列)影响算法的运行时间时，最佳情况或最坏情况是相关的。

然后运行时间是sum of geometric series (a.(r^num_terms - 1)/(r-1)):

T(n) = 2 + 4 + ... 2^(log2 n)
     = 2 . (2^log2 n - 1)
     = 2 . (n - 1)
     ⩽ 3n = O(n)

因此，您所做的工作不能超过 n 的某个常数倍数。因此，该算法的运行时间为O(n)。

您不能做一些小于某个(其他)n 的常数倍数的工作，因为您必须如上所示在内部循环中完成增量。因此，该算法的运行时间也≥c.n，即Ω(n)。

总之，这意味着该算法的运行时间为Θ(n)。