algorithm - アルゴリズム分析: ビッグ O/最悪のケース

Question

宿題の質問で、次のコード フラグメントを分析するように求められます。

for (int i = N; i > 0; i--)
    for (int j = 0; j < i; j++)

内側のループは次の回数実行されると思います。

N + (N-1) + (N-2) + ... + (N - N + 1)

ただし、それを O() 表記に変換するのに問題があります。

誰かが私を正しい方向に向けることができますか?

Answer 1

観測によると、内側のループは 1 + 2 + ... + N 回実行されます。それはまさに N(N+1)/2 (三角数の公式) です。まず、big-O の定義を思い出してください。|f/g| の場合、f は O(g) です。十分な大きさの N に制限されています。したがって、たとえば、これは O(exp(n)) であり、O(n^3) でもあります。これも O(N(N+1)/2) ですが、先生はおそらく O(N^2) という答えを期待しています。これが O(N^2) であることをどのように示しますか? (N(N+1)/2) / N^2 は 1/2 + 1/2N です。N > 0 の場合、これは 1 に制限されます。