1

これが Big O の最後の質問になることを約束します

後続のループの Big O 記法...

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           count++;
        }
     }
     for (int k = 0; k < n; k++){
        for (int m = 0; m < n; m++){
           count++;
        }
     }

ここに私が確信していると思うものがあります。

ネストされたループの最初のセットには がO(n*log2(n)) あり、ネストされたループの 2 番目のセットには がありO(n^2)ます。これらを追加するとき、最初の用語を削除するのは正しいですか? そして、全体的な Big O はO(n^2)?

2 番目の質問です。連続するループに Big O 表記を追加する場合、重要度の低い用語を削除するのは常に正しいですか?

4

2 に答える 2

4

両方の質問に対する答えはイエスです。小さい項は、十分に大きい の大きい項に支配されるため、常に破棄し、Big O 分析を行う場合nは大きいことだけを気にします。n

于 2013-01-25T03:18:28.100 に答える
1

その理由は、n*log2(n)が漸近的にによって支配される からです。n^2n|n * log2(n)| < |n^2|

これが用語を削除できることを意味する理由がわからない場合は、両側にn*log2(n)追加してみてください。n^2

n^2 + n*log2(n) < n^2 + n^2
n^2 + n*log2(n) < 2 * n^2

したがって、定数 factor を無視できることがわかっている場合、k重要度の低い項を無視できることがわかります。

于 2013-01-25T03:21:18.713 に答える