特定のBubblesortアルゴリズムの平均時間の複雑さの評価。

cs.stackexchange https://cs.stackexchange.com/questions/20

質問

Bubblesortのこの擬似コードを考慮してください。

FOR i := 0 TO arraylength(list) STEP 1  
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

平均的な時間複雑度を評価するために私が心に留めておくべき基本的なアイデアは何でしょうか？私はすでに最悪の最高のケースを計算していますが、私は式を形成するために内側ループの平均的な複雑さを評価する方法を熟考しています。

最悪の方程式は次のとおりです。

$$ sum_ {i = 0}^n left（ sum_ {j = 0}^{n - （i + 1）} o（1） + o（1） right）= o（ frac {n ^2} {2} + frac {n} {2}）= o（n^2）$$

内側のシグマは内側のループを表し、外側のシグマは外側のループを表します。 「if-then-break」 - clauseのために両方のシグマを変更する必要があると思います。 （4つのアクション + 1比較真の場合、それ以外の場合は1つの比較）。

用語の平均タイムの明確化のために：このソートアルゴリズムは、（同じ長さの）異なるリストで異なる時間が必要になります。これは、アルゴリズムが完全に順番になるまでループを通過/内部で多かれ少なかれステップを必要とする可能性があるためです。必要なラウンドの平均を評価する数学的（統計的ではない方法）を見つけようとします。

このために、私はどんな順序も同じ可能性があると期待しています。

役に立ちましたか？

解決

長さ$ n $のリストの場合、平均は通常、すべての$ n！$の順列の均一な分布から始める必要があることを意味します[$ 1 $、..、$ n $]：それはあなたが考慮する必要があるすべてのリストになります。

あなたの平均的な複雑さは、すべてのリストのステップ数の合計を$ n！$で割ったものになります。

特定のリスト$（x_i）_i $の場合、アルゴリズムのステップ数は$ nd $です。ここで、$ d $は要素$ x_i $と彼の正当な場所$ i $の間の最大の距離です（ただし、必要な場合のみです左に移動します）、つまり$ max_i（ max（1、i-x_i））$です。

次に、数学を行います。各$ d $について、この特定の最大距離でリストの番号$ c_d $を見つけます。$ d $の期待値は次のとおりです。

$$ frac1 {n！} sum_ {d = 0}^n { dc_d} $$

そして、それは$ c_d $を見つけた最も難しい部分のない基本的な考えです。たぶん、より簡単な解決策があるかもしれません。

編集：「予想」を追加しました

他のヒント

$ i <j $ and $ a [i]> a [j] $の場合、ペア$（a [i]、a [j]）$（resp。$（i、j）$）が反転していることを思い出してください。

アルゴリズムが各反転に対して1つのスワップを実行すると仮定すると、アルゴリズムの実行時間は反転数に依存します。

均一なランダム順列での逆数の予想数を計算するのは簡単です。

$ p $を順列とし、$ r（p）$と$ p $の逆とします。たとえば、$ p = 2,1,3,4 $の場合、$ r（p）= 4,3,1,2 $。

インデックス$（i、j）$の各ペアについて、$ p $または$ r（p）$の1つに反転があります。

ペアの総数は$ n（n-1）/2 $であり、総数と各ペアは順列の正確な半分で反転しているため、すべての順列が等しく可能性が高いと仮定すると、予想される反転数は次のとおりです。

$$ frac {n（n-1）} {4} $$

スワップの数<反復数（最適化されたものと単純なバブルケースシナリオの両方）

反転数=スワップ数。

したがって、反復数> $ frac {n（n-1）} {4} $

したがって、平均的なケースの複雑さは$ omega（n^2）$です。しかし、平均ケースは最悪のケースを超えることができないため、$ o（n^2）$であるとわかります。

これにより：平均時間= $ theta（n^2）$

（時間の複雑さ=反復数の反復>スワップのno。

このドキュメントでは、バブルソートの平均時間の複雑さがO（nlog（n））に達しました！http://algo.inria.fr/flajolet/publications/vifl90.pdf

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top