このソートアルゴリズムの複雑さの分析

Question

マージソートは、任意の長さのリストをソートする最良の方法ですが、現在の方法を最適化する方法は不思議です。

def sortList(l): 
    ''' 
    Recursively sorts an arbitrary list, l, to increasing order. 
    ''' 
    #base case. 
    if len(l) == 0 or len(l) == 1: 
     return l 

    oldNum = l[0] 
    newL = sortList(l[1:]) #recursive call. 

    #if oldNum is the smallest number, add it to the beginning. 
    if oldNum <= newL[0]: 
     return [oldNum] + newL 

    #find where oldNum goes. 
    for n in xrange(len(newL)): 
     if oldNum >= newL[n]: 
      try: 
       if oldNum <= newL[n+1]: 
        return newL[:n+1] + [oldNum] + newL[n+1:] 

      #if index n+1 is non-existant, oldNum must be the largest number. 
      except IndexError: 
       return newL + [oldNum] 

この機能の複雑さはどの程度ですか？私はO（n^2）を考えていたが、私は確信が持てなかった。また、この手順をさらに最適化する方法はありますか？ （それを捨てて、マージソートに行く以外に！）。

Answer 1

コードを最適化する場所がいくつかあります。

• 多くのリストコピーがあります。スライスするたびに、リストの新しいコピーを作成します。これは、配列のどこからソートを開始するかを示すインデックスを関数宣言に追加することで回避できます。
• sortListではなく、sort_listの名前を付けてPEP 8に従ってください。
• 挿入を行うコードはちょっと変わっています。アウトオブバウンドインデックスの例外を意図的に上げることは、通常のプログラミングの練習ではありません。代わりに、適切な場所に置かれるまで値を配列に上げてください。これらの変更を適用する

は、このコードを与える：

def sort_list(l, i=0): 
    if i == len(l): return 
    sort_list(l, i+1) 
    for j in xrange(i+1, len(l)): 
     if l[j-1] <= l[j]: return 
     l[j-1], l[j] = l[j], l[j-1] 

この今その場で配列をソートし、その戻り値はありません。

ここではいくつかの簡単なテストです：

cases = [ 
    [1, 2, 0, 3, 4, 5], 
    [0, 1, 2, 3, 4, 5], 
    [5, 4, 3, 2, 1, 1] 
] 

for c in cases: 
    got = c[:] 
    sort_list(got) 
    if sorted(c) != got: 
     print "sort_list(%s) = %s, want %s" % (c, got, sorted(c)) 

お勧めとして、時間の複雑さは、O（N^2）で、nは、リストの長さです。私のバージョンではO（n）の追加メモリが使用されていますが、リストは各段階でコピーされるため、O（n^2）が使用されます。

メモリ使用量をさらに向上させるもう1つのステップは、再帰を排除することです。

def sort_list(l): 
    for i in xrange(len(l)-2, -1, -1): 
     for j in xrange(i+1, len(l)): 
      if l[j-1] <= l[j]: break 
      l[j-1], l[j] = l[j], l[j-1] 

これは再帰バージョンとまったく同じですが、繰り返し実行されます。最初に配列の最後の2つの要素をソートし、最後の3つをソートし、最後の4つをソートします。

これでも実行時の複雑さはO（n^2）ですが、現在はO（1）の追加メモリが使用されています。また、再帰を避けるということは、Pythonの悪質な再帰制限を打ち切ることなく、長いリストをソートできることを意味します。もう1つの利点は、このコードが（配列が既にソートされている）最良の場合のO（n）になっていることです。

Answer 2

若いオイラーは、ここで適切と思われる式を思いついた。話は、小学校では先生が非常に疲れていて、クラスをしばらく忙しく保つために、0から100までのすべての数字を足し合わせるように言われました。ヤングオイラーはこれに戻ってきた：これはここに適用され

あなたの実行時間があるため、最悪の場合にはあなたのリストの長さまでのすべての数字の合計に比例するとしているので、あなたの関数は既にソートされたリストをソートし、リストの最後にある次の要素の位置を見つけるために毎回newLの長さをたどります。