1


次の方程式を持つ選択ソートの時間計算量を見つけようとしています
T(n)=T(n-1)+O(n)

最初に、T（n）= T（n-1）+ n .. nの方が簡単だと思いましたが、..
計算 するT(n-1) = T(n-2) + (n-1) と 、（3）..の代わりに.. KにT(n-2) = T(n-3) + (n-2)

なり、nk> = 0 .. = =>そして式に戻るその..それは..それを..それでそのO（n ^ 2）..は私がrytしたことですか??T(n) = (T(n-3) + (n-2)) + (n-1) + nT(n) = T(n-3) + 3n - 3

T(n) = T(n-k) + kn - k

n-k = 0n=k

T(n) = T(0)// which is C + n*n - n

C + n^2 -n

4

2 に答える 2

1

はい、あなたの解決策は正しいです。O（n）をO（n-1）、O（n-2）...と組み合わせて、O（n ^ 2）を考え出します。適用できますO(n) + O(n-1) = O(n)が、有限です。シリーズでは違います。

T(n) = (0 to n)Σ O(n - i)

O（）内のiを無視すると、結果はO（n ^ 2）になります。

あなたが与えた漸化式T(n)=T(n-1)+O(n)は、選択ソートに当てはまります。選択ソートは、全体的な時間計算量がO（n ^ 2）です。このリンクをチェックして確認してください

于 2013-03-03T17:30:39.597 に答える
0 
In selection sort:

反復iでは、残りの最小エントリのインデックス最小値を見つけます。そして、a[i]とa[min]を交換します。

そのため、選択ソートは

(n-1)+(n-2)+....+2+1+0 = (n-1)*(n-2)/2 = O(n*n) compares

and exactly n exchanges(swappings).

上から

そして、上記の漸化式から

=> T(n) = T(n-1)+ O(n)
=> T(n) = T(n-1)+ cn, where c is some positive constant
=> T(n) = cn + T(n-2) + c(n-1)
=> T(n) = cn + c(n-1) +T(n-3)+ c(n-2)

そしてこれは続き、私たちはついに

=> T(n) = cn + c(n-1) + c(n-2) + ...... c (total no of n terms)
=> T(n) = c(n*(n-1)/2)
=> T(n) = O(n*n)

編集

theta（n）をcnに置き換えることをお勧めします。ここで、cは定数です。方程式をより簡単に視覚化するのに役立ちます。

于 2013-03-03T17:31:55.330 に答える