big-o - 如何为循环找到Big-O表示法？

我很难找到这段代码的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;
}

最佳答案

分别考虑两个循环:

首先让我们考虑在每次迭代中使用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)(请记住，您可以忽略对数的底数)。

关于big-o - 如何为循环找到Big-O表示法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22046019/