是否有排序算法排序O（∞）排列？

在閱讀this question並通過回答中提出的各種電話簿分類情景後，我發現BOGO排序的概念非常有趣。當然，這種類型的排序算法沒有用，但它確實在我的腦海裏提出了一個有趣的問題 - 它們可能是一個無法完成的排序算法嗎？是否有排序算法排序O（∞）排列？

換句話說，是否有一個過程可以嘗試比較和重新排序一組固定的數據，但卻永遠無法實現實際的排序列表？

這是一個理論/哲學問題，而不是一個實際的問題，如果我更像是一個數學家，我可能會證明/反駁這種可能性。有沒有人問過這個問題，如果有的話，可以說什麼呢？

來源

2011-08-04 RLH

'while（true）{}'will do。 – Vlad

可能的重複[是否有任何更糟糕的排序算法比Bogosort（又名猴排序）？]（http://stackoverflow.com/questions/2609857/are-there-any-worse-sorting-algorithms-than-bogosort-aka -monkey-sort） –

@Vlad。這不是一個算法。對不起，沒有要點。 – RLH

沒有確定性的過程與有限的狀態量取「O（無窮大）」，因爲最慢的可能是通過所有可能的狀態。這包括分類。

[更早，更具體的回答：] 沒有。對於大小爲n的列表，您只有n個狀態空間！在其中存儲進度（假設整個排序狀態存儲在元素的順序中，並且確實是「做某事」）。

所以最終可能的行爲會在終止之前循環所有可用的狀態，並且需要的時間與n成正比！（冒着混淆的風險，必須有一條通過該州的路徑 - 因爲那是「所有州」，你不能有一個過程從狀態X轉移到Y，然後再從狀態X轉移到Z，因爲這需要附加狀態，或者是不確定的）

來源

2011-08-04 19:18:31

如果程序只允許使用O（N）空間並且沒有輸入或輸入數據以外的隨機源，那麼您的聲明是正確的。另一方面，誰說該計劃僅限於使用O（N）暫存空間？ – supercat

但是你打開「任何事情」的問題。例如：我定義了一種排序來運行整個宇宙的模擬，然後進行快速排序。對於這個問題的重點，我認爲這個限制是必要的。但你可以將它擴展到與n成比例的空間，但仍然沒有「無限」時間;除非您擁有「無限」的臨時空間量，否則基本參數不會改變。 –

「排除整個宇宙的模擬」的方式是指定執行必須完全確定相對於大小爲N的輸入數據流。有一些未解決的問題會終止某些輸入，但是不適用於其他算法，算法終止前可能需要的存儲量沒有上限。我不知道的是，是否有任何算法保證終止所有輸入，但是所需時間和空間不能在有界時間內計算。 – supercat

理念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)是給定足夠大的x和一些常數M的上限。

通常當你談論「無窮大」時，你正在談論某種無限制的限制。所以在這種情況下，唯一合理的定義是說O(infinity)是O(function that's larger than every function)。顯然，比每個函數都大的函數是一個上限。因此，技術上一切都是「O(infinity)」

理念3

假設你的意思THETA符號（緊約束）...

如果強加額外的限制，該算法是智能（時返回找到一個排序的排列），列表中的每個排列必須在有限的時間內訪問，然後回答no。列表只有N!排列。這樣的排序算法的上限是有限數量的有限數量的有限數量。

來源

2011-08-04 19:18:55 tskuzzy

爲什麼你需要'quicksort'呢？ – Vlad

@Vlad：在他的問題陳述中，他要求提供一種「嘗試比較和重新排序固定數據集」的排序算法:) – tskuzzy

您能否更精確地定義「嘗試」？ – Vlad

這個怎麼樣：

開始的第一個項目。
翻轉一枚硬幣。
如果是頭部，請使用下一個項目進行切換。
如果是尾巴，不要切換它們。
如果列表已排序，請停止。
如果不是，移動到下一對...

這是一個排序算法 - 種猴子可能會做。有沒有保證你會到達一個排序列表？我不這麼認爲！

來源

2011-08-04 19:20:26 John

這是比排序算法更多的排序過程（沒有定義的終止）。我認爲排序列表將以概率1發生。有趣的部分是檢測何時您有一個可以停止。 –

這幾乎是OP提到的Bogosort算法;它實際上「幾乎肯定」終止（即用P（排序）== 1）。 – dlev

有 -

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

    return SortNumbers(collectionOfNumbers) 
}

來源

2011-08-04 19:21:14 YetAnotherUser

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-04 19:23:54 Patrick87

是否有任何算法可以顯示終止，但其最壞情況下的運行時間和空間要求可以顯示爲在任何形式的有限時間內無法計算的？ – supercat

你的問題並沒有太多的與排序。一個保證永遠不會完成的算法會非常枯燥。事實上，即使是一種可能或可能不會完成的算法都會很枯燥。更令人感興趣的是最終可以保證完成的算法，但是其關於輸入大小的最壞情況計算時間不能用任何可能本身的函數F表示爲O（F（N））在有界時間內計算。我的預感是可以設計出這樣的算法，但我不知道如何。

來源

2011-08-04 19:34:15 supercat

讓我們假設你有一個隨機投幣器，無限算術和無限理性。那麼答案是肯定的。你可以編寫一個排序算法，它有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-04 21:02:31 btilly

是否有排序算法排序O（∞）排列？

回答

相關問題