ランタイム分析ソート

Question

私は、この挿入ソートアルゴリズムの実行時間分析を計算しようとしています：

1) n = length[A] 
2) count = 0 
3) for (i=1; i<=n; i++) 
4)  for (j=1; j<=i; j++) 
5)   if A[j] <= 100 
6)    for (k=j; k<=j+2*i; k++) 
7)     A[j] = A[j]-1 
8)     count = count+1 
9) return (count) 

私は次のようにユーチューブにいくつかのvideoesを見てきた：https://www.youtube.com/watch?v=tmKUHLs21PU 私も本を読んで読んで、私いますこれに類似したオンラインのものは見つけられません（3つのforループとif文のために）。

今、私は

（TJ）nが3行目のランタイムが Nあり、そして4のために、それは ΣのJ = 1であることを理解し

5のような程度まで、私はかなり良いですよ

私は完全に失われているので、私はΣがif文に関係していることを知っています。誰かが次に何をすべきか、それがなぜそうなのかを詳しく説明できますか？ありがとうございました。

Answer 1

これは宿題によく似ていますが、あなたにすべての答えを与えるだけの好意はありませんが、残念ながら自分で残りの部分を把握するのに役立ついくつかの原則があります。

行4は、外側ループを最初に1回、2回目を2回、ループを介してn回目にn回まで発生します。 、漸近複雑さの点では

1 + 2 + ... (n-1) + n 
= (n + 1) + (n - 1 + 2) + ... + (n - n/2 + n/2 + 1) 
= (n + 1) + (n + 1) + ... + (n + 1) 
= (n + 1) * n/2 
= n²/2 + n/2 

：我々はこれらが、一緒に2番目と最後から2番目の最初と最後の加数を入れて並べ替える場合

1 + 2 + ... + n 

は、我々はパターンを見ます定数1/2およびnはn²よりも大きいので、4行目のbig-Oはn²です。

行5は、評価する行数に関係なく、行番号4を実行する回数だけ評価する必要があります。つまり、n²になります。しかし、その内部の行が何度実行されるかは、配列の値によって異なります。これは、最善のケースと最悪のケースの複雑さに遭遇するところです。

最良のケースでは、アレイ内の値は、常に100よりも大きくなるので、全体アルゴリズムの複雑さは、最悪の場合、A[j]の値の行の複雑5

に等しいです。常に100以下であるため、ライン6のforループが評価され、アルゴリズム全体の複雑さが増します。

残りの線が全体的な複雑さにどのように影響するかを把握するために残しておきます。

そして、これは私に挿入するようなものではありません。配列の値を互いに比較するのではなく、配列内の位置を入れ替えます。配列の値を定数（100）と比較し、配列内の位置に基づいて値を減らしています。