BigO整数のランタイムの合計

Question

私はBig Oを勉強しようとしていますが、私が今直面したアルゴリズムについて混乱しています。アルゴリズムは次のとおりです。

void pairs(int[] array){ 
    for (int i=0; i < array.length; i++){ 
    for (int j=i+1; j<array.length; j++){ 
     System.out.println(array[i]+","+array[j]); 
    } 
    } 
} 

私はループの最初はO(n)であると私は2番目のforループはO(1/2*n(n+1))である知っていると思います。問題の答えは、関数の実行時間がO(n^2)であるということでした。私はO(1/2*n(n+1))をO(1/2*(n^2+n))に簡略化しました。だから私は、forループがネストされているので、2つのランタイム条件を掛ける必要があると思ったので混乱しています。これはO(n) * O(1/2*(n^2+n))となります。私はこれをO(1/2n^3 + 1/2n^2)に簡略化しました。私がビッグ・オーのことを理解してから、あなたは最大の用語だけを保持するので、これはO(n^3)に縮小されます。誰かが私が間違ったところで私を助けることができますか？答えがO(n^3)ではなくO(n^2)であるかどうか不明です。

Answer 1

内部ループがO(1/2*n(n+1))であると言うと、実際にはのbig-Oの複雑さが記述されています。ループです。

外側のループが複雑であると言うと、O（N）は基本的にボディがN回実行されることを意味します。しかし、内部ループの複雑さを計算するには、すべての外側ループの反復回数を考慮しました。これは、内側ループが外側ループのすべての反復にわたって実行される回数を合計したためです。もう一度N倍にすると、外側のループ自体が別のN回再実行されるということになります。

あなたの分析が示していることは、内側ループ本体（System.out.println呼び出し）が全体的に1/2*n(n+1)回実行されていることです。つまり、2ループの組み合わせの全体的な複雑さはO(1/2*n(n+1)) = O(n^2)です。 2ループの組み合わせの全体的な複雑さは、最も内側のコードが何回実行されるかを表します。

Answer 2

あなたのミスが最初
... O(1/2n^2)ように、第2のループをカウントしている、あなたは

最初のループ明確N
第二のループがMAXである（J = 0のとき）それはN-1にキャップされるはっきりと見ることができますN-1の...
threrefore、O（N^2）...

は、我々はそれがもう少し、 第二のループを実行する調べる場合N-1i=0、
i=1ため、その後N-2、
とONE単一の時間i=n-1ため、

この1/2n(n-1) = 1/2n^2 - 1/2n = O(n^2)
お知らせが、これは外側のループのすべての反復をあまりにも含まれています！