复杂性计算

什么是复杂性:

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？

有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)