algorithm - 一个循环重复对一个值求平方和一个循环重复乘以三的时间复杂度？

Question

我需要一种方法来计算以下循环的 Big-theta 边界，但我不确定能否找到一种模式:

public static in sumCalc(int n) {
  int k=3;
  int sum =0;
  while (n>0) {
     for (int i=2; i<k; i=i*i)
       sum = sum+i
     n--
     k=k*3
  }
  return sum;
}

我可以看到外循环将执行 n 次，但很难找到内循环将执行多少次。 我试图通过追踪它来找到一种模式，并想出了这样的事情:

   n value   k value     #of times inner loop executes
--------------------------------------------------------
   n         k=3         1
   n-1       k=3^2       2
   n-2       3^3         3
   n-3       3^4         3
   n-4       3^5         3
   n-5       3^6         4
   ...
   n-9       3^10        4
   n-10      3^11        5
   ...

我不确定这里是否存在模式。我无法编写求和公式来计算此表中内循环的总执行情况。 直觉上，我认为外循环将执行 O(log n) 次，而内循环将执行 O(sqrt(n))。所以答案可以是 O(sqrt(n)*log n) ?

Answer 1

这很有趣!要解决这个问题，我们需要一些数学工具，但最重要的是我们需要这条格言:

When in doubt, work inside-out!

也就是说，让我们采用最内层的循环，计算出它做了多少工作，然后重复删除它并用一个占位符替换它，指示完成了多少工作。

我们最里面的循环看起来像这样:

for (int i=2; i<k; i=i*i)
   sum = sum+i

这个循环内部的复杂度为 O(1)，所以我们需要做的就是计算出迭代次数。这归结为这个问题:在超过某个数 k 之前，您可以对一个数进行多少次平方(从 2 开始)？

为了找出答案，让我们假设我们正处于循环的第 j 次迭代。此时 i 的值是多少？嗯，

• 在第一次迭代开始时 (j = 0)，i = 2 = 2¹。
• 在第二次迭代开始时 (j = 1)，i = 4 = 2²。
• 在第三次迭代开始时 (j = 2)，i = 16 = 2⁴。
• 在第四次迭代开始时 (j = 3)，i = 256 = 2⁸。

注意到一个模式了吗？每次我们对 i 进行平方时，我们都会将 2 的幂指数加倍。这意味着指数本身呈指数级增长，如果您像这样写出数字，就更容易看出这一点:

• 在第一次迭代开始时 (j = 0)，i = 2 = 2¹ = 2²⁰。<
• 在第二次迭代开始时 (j = 1)，i = 4 = 2² = 2²¹。<
• 在第三次迭代开始时 (j = 2)，i = 16 = 2⁴ = 2²²。<
• 在第四次迭代开始时 (j = 3)，i = 256 = 2⁸ = 2²³。<

更一般地，在循环的第 j 次迭代中，i 的值为 2^2j。并且循环将一直运行直到 j 的相应值结束超过 k。解决，我们得到这个:

2^2j = k

2^j = lg k

j = lg lg k

换句话说，这个循环将运行 Θ(log log k) 次。这是一个难以置信的小次数，你需要 k 非常大才能让它运行任何合理数量的迭代。作为引用，lg lg A，其中 A 是已知宇宙中的粒子数，约为 8。

请注意，在这里看到日志日志并不意外。如果您反复将 1 加到一个数量上，则需要 O(k) 次迭代才能超出数字 k。如果你反复加倍一个数字直到超过数字 k，那么你将需要 O(log k) 次迭代才能完成。如果您重复对一个数 k 求平方，则需要 O(log log k) 次迭代。

因此，如果我们跳回原始代码，我们可以像这样删除并重写该内部循环:

  int k=3;
  while (n>0) {
     do Theta(log log k) work;
     n--;
     k=k*3;
  }

那现在呢？好吧，我们知道这个外层循环会运行 n 次。但是完成的总工作量是多少？我们可以看到这里取的 k 值呈指数增长:第一次迭代时 k 为 3，第二次迭代时为 9，第三次迭代时为 27，等等。更一般地，它的值为 3^j 在第 j 次迭代中。这意味着我们可以通过将 k 取的所有值相加 log log k 来总结这个 while 循环所做的工作。这给出了以下内容:

log log 3 + log log 3² + log log 3³ + ... + log log 3ⁿ

= log log 3 + log (2 log 3) + log (3 log 3) + ... + log (n log 3) (power rule for logarithms)

= log((log 3) · (2 log 3) · (3 log 3) · ... · (n log 3)) (sum rule for logarithms)

= log ((1 · 2 · 3 · ... · n)(log 3 · log 3 · log 3 ... · 3)) (regrouping terms)

= log (n! · (log 3)ⁿ (simplifying)

= log (n!) + n log log 3 (sum and power rules)

= Θ(n log n) + n log log 3 (Stirling’s approximation)

= Θ(n log n).

所以总的功是 Θ(n log n)。

现在，这里要注意的一个细节是，这假设 k 和 i 的值永远不会溢出，这通常不是一个安全的假设。实际上，对于任何合理的 n 值，此函数都会开始表现得很奇怪。但为了简单起见，我们暂时忽略它。 :-)