0

現在立ち往生している例はほとんどありません。あなたのアドバイスとこれを行う方法をいただければ幸いです。これらの例の最良のケースと最悪のケースは何ですか?

  • 例 1

例 1

  • 例 2

例 2

  • 例 3

例 3

4

2 に答える 2

2

私はあなたに答えを与えるつもりはありません。しかし、これは私がコメントでそれにアプローチする方法の例です。

for(int i = 0; i < N; i++) //This line is executed N times

    for(int j = i; j < N; j++) // This line is executed (N - i) times, for every N

         doSomeWorkOn(i, j);  //This can add complexity as well, but let's assume we're trying to figure out how many times this is called.

したがって、最初のループを実行するたびに、2 番目のループで行う作業の量が減少することに注意してください。これは事態を複雑にします。内部ループが読み取った場合

for(int j = 0; ......)

答えは簡単です。単純に N * N です。N 回、N 量の作業を行う必要があります。この場合、私たちが持っているのは

N + (N-1) + (N-2)....(NN) その後、数学的シリーズをグーグルで検索すると、これが (N(N+1))/2 に単純化されることがわかります。

編集：

私がやったのとは逆にすると、おそらくシリーズを見つけやすくなることに注意してください。つまり、

0+1+2+...(N) = N + (N-1) + (N-2) ... (0) = (N(N+1))/2

最初のアプローチが最も一般的です。級数表を覚えているので逆にする癖があり、それを N との関係で見る方が私には意味がありますが、初心者の観点から言えば、下端から始める方が簡単です。これは、ほとんどのヘルプ ページ/教科書/教授が提示する方法です。ただし、同一です。あなたにとって最も簡単な方法です。

于 2013-06-03T14:45:44.903 に答える
1

Algorithms クラスの宿題のように見えますが、反復アルゴリズムを分析するには、合計規則を使用する必要があります。Anany Levitin による「Introduction to the Design and Analysis of Algorithms 」は、持っておくとよい本です。

そして、ChrisCMが言ったことに沿って -

本からの引用：時間効率

役立つルール:反復アルゴリズム分析

于 2013-06-03T14:48:37.827 に答える