1

この質問を読み、回答に示されているさまざまな電話帳の並べ替えシナリオを調べた後、BOGO並べ替えの概念は非常に興味深いものであることがわかりました。確かに、このタイプの並べ替えアルゴリズムは使用できませんが、それは私の心に興味深い質問を提起しました-それらは、完了することが無限に不可能な並べ替えアルゴリズムである可能性がありますか？

言い換えると、固定されたデータセットを比較して並べ替えることができても、実際の並べ替えられたリストを実現できないプロセスはありますか？

これは実際的な質問というよりも理論的/哲学的な質問であり、私が数学者であれば、そのような可能性を証明/反証することができるでしょう。誰かが以前にこの質問をしたことがありますか？もしそうなら、それについて何を言うことができますか？

4

7 に答える 7

4

[編集：]有限量の状態を持つ決定論的プロセスは「O（無限大）」を取りません。これは、可能な限りすべての状態を進行するのが最も遅いためです。これには並べ替えが含まれます。

[以前の、より具体的な答え：] いいえ。サイズnのリストの場合、サイズnの状態空間しかありません。進行状況を保存する場所（ソートの状態全体が要素の順序で保存され、決定論的に「何かをしている」と仮定します）。

したがって、考えられる最悪の動作は、終了する前に使用可能なすべての状態を循環し、nに比例する時間がかかります。（混乱を招く恐れがありますが、状態を通る単一のパスが必要です。これは「すべての状態」であるため、プロセスを状態XからYに移動し、後で状態XからZに移動することはできません。追加の状態、または非決定論的）

于 2011-08-04T19:18:31.703 に答える
3

アイデア1：

function sort( int[] arr ) {
    int[] sorted = quicksort( arr ); // compare and reorder data
    while(true); // where'd this come from???
    return sorted; // return answer
}

アイデア2

どのように定義しますO(infinity)か？Big-Oの正式な定義は、それが与えられた十分に大きく、ある定数の上限であることをf(x)=O(g(x))意味するだけです。M*g(x)f(x)xM

通常、「無限大」について話すときは、ある種の無制限の制限について話します。したがって、この場合、唯一の合理的な定義は、それがであると言うことO(infinity)ですO(function that's larger than every function)。明らかに、すべての関数よりも大きい関数は上限です。したがって、技術的にはすべてが「O(infinity)」

アイデア3

あなたがシータ表記（タイトバウンド）を意味すると仮定すると...

アルゴリズムがスマートであり（ソートされた順列が見つかったときに戻る）、リストのすべての順列に有限の時間内にアクセスする必要があるという追加の制限を課す場合、答えはノーです。N!リストの順列のみがあります。その場合、そのようなソートアルゴリズムの上限は、有限である有限数に対する有限です。

于 2011-08-04T19:18:55.903 に答える
2

あなたの質問は、実際には並べ替えとはあまり関係がありません。決して完了しないことが保証されているアルゴリズムはかなり鈍いでしょう。確かに、完全であるかもしれないし、完全ではないかもしれないアルゴリズムでさえ、かなり鈍いでしょう。はるかに興味深いのは、最終的には完了することが保証されるアルゴリズムですが、入力のサイズに関する最悪の場合の計算時間は、それ自体が可能な関数FのO（F（N））として表現できません。制限された時間で計算されます。私の勘では、そのようなアルゴリズムを考案できると思いますが、その方法はわかりません。

于 2011-08-04T19:34:15.913 に答える
1 
  Input:      A[1..n] : n unique integers in arbitrary order
  Output:     A'[1..n] : reordering of the elements of A
              such that A'[i] R(A') A'[j] if i < j.
  Comparator: a R(A') b iff A'[i] = a, A'[j] = b and i > j

より一般的には、コンパレータを（a）出力仕様と調整できないために解決策が存在しないようにするか、（b）計算できない（たとえば、これらの（入力、チューリングマシン）ペアを次の数の順に並べ替える）ものにします。マシンが入力で停止するために必要な手順）。

さらに一般的には、有効な入力で停止できないプロシージャがある場合、そのプロシージャはその入出力ドメインの問題を解決するアルゴリズムではありません...つまり、アルゴリズムがまったくないか、またはドメインを適切に制限した場合、あなたが持っているのはアルゴリズムだけです。

于 2011-08-04T19:23:54.307 に答える
1

これはどう：

  1. 最初の項目から始めます。
  2. コインを投げます。
  3. 頭の場合は、次のアイテムに切り替えてください。
  4. 尾の場合は、切り替えないでください。
  5. リストがソートされている場合は、停止します。
  6. そうでない場合は、次のペアに移動します...

これは並べ替えアルゴリズムであり、サルが行う可能性のある種類です。ソートされたリストに到達するという保証はありますか？私はそうは思わない！

于 2011-08-04T19:20:26.277 に答える
1

はい -

SortNumbers(collectionOfNumbers)
{
  If IsSorted(collectionOfNumbers){
     reverse(collectionOfNumbers(1:end/2))     
  } 

  return SortNumbers(collectionOfNumbers)
}
于 2011-08-04T19:21:14.400 に答える
0

あなたがランダムなコインフリッパー、無限の算術、そして無限の有理数を持っていると仮定しましょう。答えはイエスです。データを正常に並べ替える可能性が100％ある（つまり、実際には並べ替え関数である）並べ替えアルゴリズムを作成できますが、平均すると、これには無限の時間がかかります。

これはPythonでのこれのエミュレーションです。

# We'll pretend that these are true random numbers.
import random
import fractions

def flip ():
    return 0.5 < random.random()

# This tests whether a number is less than an infinite precision number in the range
# [0, 1].  It has a 100% probability of returning an answer.
def number_less_than_rand (x):
    high = fractions.Fraction(1, 1)
    low = fractions.Fraction(0, 1)

    while low < x and x < high:
        if flip():
            low = (low + high) / 2
        else:
            high = (low + high) / 2

    return high < x

def slow_sort (some_array):
    n = fractions.Fraction(100, 1)
    # This loop has a 100% chance of finishing, but its average time to complete
    # is also infinite.  If you haven't studied infinite series and products, you'll
    # just have to take this on faith.  Otherwise proving that is a fun exercise.
    while not number_less_than_rand(1/n):
        n += 1
    print n
    some_array.sort()
于 2011-08-04T21:02:31.047 に答える