9

什么是复杂性:

int f4(int n)
{
   int i, j, k=1, count = 0;

   for(i = 0; i < n; i++) 
   {
      k *= 3;

      for(j = k; j; j /= 2)
         count++;
   }

   return count;
}

我知道它是 O(n^2) 但你如何计算这个?为什么不是 n*log n?

4

3 回答 3

21

有 n 个外循环。在任何时候,。有内部循环(因为我们在每次迭代中减半。)k = 3ilog2(k)j

log2(3i) = log3 (3i) / log3(2) = i / (constant)

所以内循环的复杂度是i。换句话说,这个程序具有相同的复杂性(但不完全相同的迭代次数)

int f4changed(int n)
{
   int i, j, count = 0;

   for(i = 0; i < n; i++) 
   {
      for(j = 0; j < i; j++)
      {
          count++;
      }
   }
}

正如您已经看到的那样。O(n2)

于 2009-02-15T09:23:03.817 回答
2

i = 1 导致 3 次迭代(内部循环) (3, 1, 0)
i = 2 是 8 (5 然后 3)
i = 3 是 13 (7 + 5 + 3)

您所拥有的是近似算术级数,即 O(n 2 )。

为了完整起见(并解释为什么确切的迭代次数无关紧要),请参阅Big O 的普通英语解释(这对于其他读者来说比你更适合,因为你似乎知道发生了什么,所以发帖者)。

于 2009-02-15T09:27:17.643 回答
0

Log(Pow(3,n)) ~ O(N) 的复杂度。如果内部循环是 k *= 2,那么迭代次数也将是 n。
为了计算 O(~),使用最高幂项,而忽略其他项。Log(Pow(3,n)) 可以定义为:
Log(Pow(2,n)) <= Log(Pow(3,n)) <= Log(Pow(4,n))
现在 Log(Pow( 4,n)) = 2*Log(Pow(2,n))。

这里的最高幂项是 n(因为 2 是常数)。

于 2009-02-15T09:38:04.310 回答