最良の場合のスワップと比較のためのバイナリ挿入ソートの複雑さ

Jan 18 2021

バイナリ挿入ソートの複雑さは何でしょうか?そして、いくつのスワップと比較が行われますか?

O(n(LG n))比較かもしれませんが、よくわかりません。最悪の場合、それは確かにN^2スワップです。最高はどうですか?

回答

1 wsdookadr Jan 19 2021 at 13:29

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,..,10,n-1,1,n-2,2,n-3,...)リストとinterverted()リストでどのように動作するかを確認しようとしました。そして、(matchgrowthモジュールを使用して)それらをさまざまな成長率に適合させました。この部分は単なる概算です。逆の順序は多項式時間に適合され、交互の順序は準線形時間に適合されました。

最良のケースはここで説明されています。リストがすでにソートされている場合は、スワップを実行しなくても、すべてのバイナリ検索が実行されているため、になりO(n*log(n))ます。

ここで使用されているコードは、このリポジトリで入手できます。