big-o - 如何为我的循环找到 Big-O 符号？

Question

我很难找出这段代码的 Big-O 符号。
我需要找到两个 for 循环的符号。

public static int fragment(int n)
{
  int sum = 0;

  for (int i = n; i >= 1; i /= 2)
  {
    for (int j = 1; j <= i; j *= 3)
    {
      sum++;
    }
  }

  return sum;
}

Answer 1

分别考虑两个循环:

首先让我们考虑 for(int i=n; i>=1; i/=2)在每次迭代中 i 的值将被除以 2 直到它达到小于 1 的值.因此，迭代次数 N 将等于您应该除以的次数 i来自 2在它小于 1 之前。有一个众所周知的函数表示这个数字 - log(n) .

现在让我们考虑内部循环。 for(int j=1;j<=i; j*=3) .在这里你将 j 乘以 3 直到它大于 i .如果您认为这与对第一个循环进行以下轻微修改的迭代次数完全相同:for(int j=i; j>=1; j/=3) .并且使用完全相同的解释，我们具有相同的功能(但基数不同 - 3)。这里的问题是迭代次数取决于 i。

所以现在我们的总复杂度是:

log3(n) + log3(n/2) + log3(n/4) ... + log3(1) =

log3(n) + log3(n) - log3(2) + log3(n) .... - log3(2log2(n)) =

log3(n) * log2 (n) - log3(2) - 2 * log3(2) - ... log2(n) * log3(2) =

log3(n) * log2 (n) - log3(2) * (1 + 2 + ... log2) =

log3(n) * log2 (n) - log3(2) * (log2(n) * (log2(n) + 1))/2 =

log2 (n) * (log3(n) - log3(2) * (log2(n) + 1)/2) =

log2 (n) * (log3(n) - (log3(n) + log3(2))/2) =

(log2 (n) * log3(n))/2 - (log2 (n) * log3(2))/2

计算有点棘手，我使用了对数的一些属性。然而，最终的结论是循环的复杂性 O(log(n)^2) (请记住，您可以忽略对数的底数)。