complexity-theory - 複雑さの計算

Question

次の複雑さは何ですか:

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 ではないのでしょうか?

Answer 1

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)