最良の場合のスワップと比較のためのバイナリ挿入ソートの複雑さ
バイナリ挿入ソートの複雑さは何でしょうか?そして、いくつのスワップと比較が行われますか?
O(n(LG n))
比較かもしれませんが、よくわかりません。最悪の場合、それは確かにN^2
スワップです。最高はどうですか?
回答
bisect_leftandlist.pop(..)やlist.insert(..):などの組み込み関数を利用することで、バイナリ挿入ソートを簡単に記述できます。
def bininssort(L):
n = len(L)
i,j=0,0
for i in range(1,n):
j=i-1
x=L.pop(i)
i1=bisect_left(L,x,0,j+1)
L.insert(i1,x)
return L
最悪のケースについて、であるためi-th
、ループの反復、我々は、サブアレイ内のバイナリ検索を実行するA[0..i]
と、0<=i<n
取るべきである、log(i)
私たちは今、私たちは場所に要素を挿入する必要があります知っているので、操作をi1
し、我々はそれを挿入しますが、挿入とは、それに続くすべての要素を1つ右に押す必要があることを意味します。これは、少なくともn-i
操作です(n-i
挿入場所によっては、操作よりも多くなる場合があります)。これら2つだけを合計すると、次のようになります。\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2
(上記でスターリングの近似のlog(n!)
使用されています)
今ウィキページは言う
経験則として、任意の関数の最高次の項がその成長率を支配し、したがってその実行時の順序を定義すると想定できます。
したがって、最悪の場合、バイナリ挿入ソートにはO(n^2)
複雑さが伴うという結論になると思います。
参照:
- 二分探索を使用した挿入ソート
- 二分探索による挿入ソート
- バイナリ挿入ソートの分析
- バイナリ挿入ソートと複雑さ
次に、reversed n,n-1,n-2,..,1
(0,n-1,1,n-2,2,n-3,...
)リストとinterverted()リストでどのように動作するかを確認しようとしました。そして、(matchgrowthモジュールを使用して)それらをさまざまな成長率に適合させました。この部分は単なる概算です。逆の順序は多項式時間に適合され、交互の順序は準線形時間に適合されました。
最良のケースはここで説明されています。リストがすでにソートされている場合は、スワップを実行しなくても、すべてのバイナリ検索が実行されているため、になりO(n*log(n))
ます。
ここで使用されているコードは、このリポジトリで入手できます。