0

次の C 関数の時間計算量を計算したところ、次のようになりました。theta (nlogn)私が間違っているかどうか教えていただけますか?与えられた答えはtheta(n^2logn)?私はこれらの概念について読み始めたところです。

int unk(int n)
{
  int i,j,k=0;
  for(i=n/2;i<=n;i++)
     for(j=2;j<=n;j=j*2)
        k=k+(n/2);
  return k;
}

私がやったことは次のとおりです:外側のループは(n/2+2)回実行され、内側のループは(n/2+1)(logn+1)回実行され、ループの本体のステートメントは回実行されます.(n/2+1)(logn)したがって、合計実行時間は になりtheta(nlogn)ます.(すべてのコストが1であり、ログが2 対数である必要があります)。

4

1 に答える 1

4

あなたの答えは正しいと思います、それは確かに theta(nlogn) です。しかし、あなたの分析はやや間違っているようです。

外側のループは O(n/2) 回実行されます。

内側のループは、外側のループの反復ごとに O(logn) 回実行されます。

2 つを乗算して定数を削除すると、 に到達しO(n) * O(logn) = O(nlogn)ます。

于 2013-07-29T01:32:46.340 に答える