-3

この質問が再開されることを期待して、この質問を編集しました。

まず第一に、これは課題の一部でした。

実行時間が O(log² N) に比例するメソッドを作成するように依頼されました。

log² N は log N² と同じであってはなりません。これは、log N² の割り当てに別の同様の質問があるためです。

以前の質問を検索して調べましたが、log² N について話しているトピックは見つかりませんでした。

私の推測では、log² N は、log n のネストされた for ループです。

for(int i=0; i < n; i*=2){
  for(int j=0; j < n; j*=2){
   //some code here...
  }
}

ただし、このコードは対数 N² も表す可能性があるため、正しい答えを正当化するものではありません。

したがって、log² N に関するガイダンスや、O(log² N) で実行されている可能性のあるアルゴリズムの例を教えてください。

これにより私の質問がより明確になり、この質問を再開できるようになったことを願っています。

4

1 に答える 1

3

このようなものは次の複雑さを持ちますO(n) = log^2(n):

for(int i = 1; i < n; i = i * 2)
{
    for(int j = 1; j < n; j = j * 2)
    {
        //Code
    }
}
于 2012-10-11T23:58:01.227 に答える