10

私は自分のアミューズメント用に O(n!) ソートを作成しました。これは、完全に置き換えずに高速に実行するために簡単に最適化することはできません。[いいえ、ソートされるまでアイテムをランダム化しただけではありません]。

時間の複雑さを軽減するために引き抜くことができる無関係なジャンクを追加するだけでなく、さらに悪い Big-O ソートを作成するにはどうすればよいでしょうか?

http://en.wikipedia.org/wiki/Big_O_notationには、さまざまな時間の複雑さが大きくなる順に並べられています。

編集:コードを見つけました。これは、リストのすべての組み合わせのリストを生成する面白いハックを使用した O(n!) 決定論的ソートです。反復可能な組み合わせを返す get_all_combinations の少し長いバージョンがありますが、残念ながら単一のステートメントにすることはできませんでした。[以下のコードでタイプミスを修正し、アンダースコアを削除して、バグが発生していないことを願っています]

def mysort(somelist):
    for permutation in get_all_permutations(somelist):
        if is_sorted(permutation):
            return permutation

def is_sorted(somelist):
    # note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf)
    if (len(somelist) <= 1): return True
    return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:]))

def get_all_permutations(lst):
    return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]
4

8 に答える 8

9

「乗算と降伏」パラダイムを使用し、指数時間で実行される、スロー ソートと呼ばれる (証明済みの) 最悪のソート アルゴリズムがあります。

アルゴリズムは遅くなりますが、着実に進行するのではなく、ランダムなジャンプを実行します。さらに、スローソートの最良のケースは依然として指数関数的ですが、あなたのケースは一定です。

于 2008-08-25T10:58:09.297 に答える
3

Chrisと私は、別の質問でBozosortとBogosortについて言及しました。

于 2008-08-25T02:11:36.143 に答える
2

O(∞) である NeverSort が常に存在します。

def never_sort(array)
  while(true)
  end
  return quicksort(array)
end

PS:決定論的な O(n!) ソートを本当に見たいです。O(n!) であるとは考えられませんが、古典的な計算では上限が有限です (別名、決定論的です)。

PPS: コンパイラがその空の while ブロックを一掃することを心配している場合は、ブロックの内外で変数を使用して強制的に消去しないようにすることができます。

def never_sort(array)
  i=0
  while(true) { i += 1 }
  puts "done with loop after #{i} iterations!"
  return quicksort(array)
end
于 2008-08-25T03:00:59.100 に答える
1

いつでもランダムソートを行うことができます。すべての要素をランダムに再配置し、ソートされているかどうかを確認することで機能します。そうでない場合は、ランダムにそれらを再利用します。それがbig-O表記にどのように適合するかはわかりませんが、間違いなく遅くなります。

于 2008-08-26T13:57:17.000 に答える
1

これは、取得できる最も遅い有限ソートです。

Quicksort の各操作を Busy Beaver 機能にリンクします。

4 つ以上の操作を取得するまでに、上矢印表記が必要になります :)

于 2008-10-07T13:15:37.737 に答える
0

n個の整数のすべての配列tをループするのはどうですか（整数のnタプルは可算なので、もちろん無限ループですが、これは実行可能です）。

  • その要素が正確に入力配列の要素であり（以下のalgoを参照）、配列が並べ替えられている場合（たとえば、線形アルゴリズムですが、もっと悪いことができると確信しています）、tを返します。
  • それ以外の場合はループを続行します。

長さnの2つの配列aとbに同じ要素が含まれていることを確認するには、次の再帰アルゴリズムを使用します。0とn-1の間のインデックスのすべてのカップル（i、j）をループし、そのようなカップルごとにループします。

  • a [i] == b [j]かどうかをテストします：
  • その場合、aからa [i]を削除し、bからb [j]を削除して取得したリストの再帰呼び出しがTRUEを返す場合にのみ、TRUEを返します。
  • カップルをループし続け、すべてのカップルが完了した場合は、FALSEを返します。

時間は、入力配列内の整数の分布に大きく依存します。

真剣に、しかし、そのような質問へのポイントはありますか？

編集：

@Jon、ランダムソートは平均してO（n！）になります（n！の順列があるため、正しいものを見つける確率は1 / n！です）。これは、個別の整数の配列にも当てはまります。一部の要素が入力配列に複数回出現する場合はわずかに異なる可能性があり、入力配列の要素の分布（整数）に依存します。

于 2008-08-26T13:33:58.990 に答える
0

私が考えることができる 1 つの方法は、関数を使用して各要素のポスト位置を計算し、大きな要素を最後に、小さな要素を最初に徐々に移動することです。トリガー ベースの関数を使用した場合、要素を最終位置に直接移動させるのではなく、リストを介して接触させることができます。セット内の各要素を処理したら、完全なトラバーサルを実行して、配列がソートされているかどうかを判断します。

これで O(n!) が得られるとは確信していませんが、それでもかなり遅いはずです。

于 2008-08-25T02:18:43.413 に答える
0

多くのコピーを行うと、「合理的な」ブルート フォース検索 (N!) を取得して、ケースごとに N^2 時間をかけて N!*N^2 を得ることができると思います。

于 2008-08-25T03:23:09.280 に答える