次の挿入ソート アルゴリズムを使用します。
調べると、O(n^2) はかなり簡単であることがわかります。しかし、それが O(n^2) であることを証明するにはどうすればよいでしょうか? すべての操作を合計することはできますが、n + "sum of j=2 to n"私の知る限り、実際には n^2 にはなりません。
これを正確に証明する方法がわかりません。O（n ^ 3）アルゴリズムでも機能する方法で、これを証明する方法を誰かが明確に説明してもらえますか？
質問する
2553 次
3 に答える
2
最悪の場合に実行される操作の数を考慮すると、非常に複雑であることが証明されます。カウント部分を実行し、画像の右側の列に結果を入力したので、証明されなければならないことは、支配的な用語がO(n^2).
合計を含む項とは別に、プログラムは実行n-1回数を取得する命令で構成されているため、これらはすべてO(n)項です。
次に、合計の条件について説明します。最悪の場合、aに設定した値を 0まで減らしてしまう可能性があるため、at_jになる可能性があります。したがって、この最悪のケースでは、a を持つ項があり、これはです。これは、数学的恒等式に従うためです。jijt_j = jsum from 2 to n of jO(n^2)
これは、これらの級数の 2 つを合計し、合計が になる 2 つの項を追加するように注意してからn+1、合計を 2 で割ることによって証明できます。wolfram の証明を見てください。
最後にO((n^2 + n)/2) = O(n^2)、合計を含む用語がランタイムを支配することがわかったので、アルゴリズムがO(n^2)
于 2013-09-24T15:04:41.787 に答える