是否存在以 O(∞) 排列进行排序的排序算法？

Question

阅读这个问题并通过中提出的各种电话簿排序场景后回答，我发现 BOGO 排序的概念非常有趣。当然，这种类型的排序算法没有任何用处，但它确实在我脑海中提出了一个有趣的问题——它们是否是一种无限不可能完成的排序算法？

换句话说，是否有一个过程可以让人们尝试比较和重新排序一组固定的数据，但永远无法获得实际的排序列表？

这更多的是一个理论/哲学问题，而不是一个实际问题，如果我更像是一名数学家，我可能能够证明/反驳这种可能性。以前有人问过这个问题吗？如果有，可以说什么呢？

Answer 1

[编辑：] 具有有限状态量的确定性过程不会采用“O(无穷大)”，因为它最慢的速度就是遍历所有可能的状态。这包括排序。

[之前更具体的答案：]
不。对于大小为 n 的列表，您只有大小为 n 的状态空间！在其中存储进度（假设排序的整个状态存储在元素的排序中，并且它确实确定性地“做某事”）。

因此，最糟糕的可能行为将在终止之前循环遍历所有可用状态，并且花费与 n 成正比的时间！ （冒着混淆问题的风险，必须有一条通过状态的单一路径 - 因为这是“所有状态”，所以您不能让进程从状态 X 移动到 Y，然后再从状态 X 移动到 Z，因为这需要附加状态，或者是不确定的）

Answer 2

想法 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(无穷大)？ Big-O 的正式定义仅指出 f(x)=O(g(x)) 意味着 M*g(x) 是 的上限code>f(x) 给定足够大的 x 和一些常数 M。

通常，当您谈论“无穷大”时，您正在谈论某种无限的限制。因此，在这种情况下，唯一合理的定义是 O(无穷大) 是 O(比每个函数都大的函数)。显然，大于每个函数的函数就是上限。因此，从技术上讲，一切都是“O(infinity)”

想法 3

假设您的意思是 theta 表示法（紧界）...

如果您施加额外的限制，即该算法是智能的（当找到排序的排列时返回）并且列表的每个排列必须在有限的时间内被访问，那么答案是否定的。列表只有 N! 种排列。这种排序算法的上限是有限数上的有限数，它是有限的。

Answer 3

你的问题实际上与排序没有太大关系。保证永远不会完成的算法将是相当乏味的。事实上，即使是一个可能会或可能永远不会完成的算法也会相当乏味。更有趣的是一种算法，它最终可以保证完成，但对于任何函数 F 来说，其相对于输入大小的最坏情况计算时间都不能表示为 O(F(N))在有限时间内计算。我的预感是可以设计出这样的算法，但我不确定如何设计。

Answer 4

这个怎么样：

1. 从第一项开始。
2. 抛一枚硬币。
3. 如果是正面，则与下一个项目交换。
4. 如果是尾巴，不要交换它们。
5. 如果列表已排序，则停止。
6. 如果没有，则继续下一对……

这是一种排序算法——猴子可能会做的那种算法。是否能保证您会得到一个已排序的列表？我不这么认为！

Answer 5

是的 -

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

  return SortNumbers(collectionOfNumbers)
}

Answer 6

  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）不可计算（例如，按照数量的顺序对这些（输入，图灵机）对进行排序机器在输入时停止所需的步骤）。

更一般地说，如果您的程序无法在有效输入上停止，则该程序不是解决该输入/输出域问题的算法......这意味着您根本没有算法，或者如果你适当地限制域，你所拥有的只是一种算法。

Answer 7

假设您有一个随机的硬币翻转器、无限的算术和无限的有理数。那么答案是肯定的。您可以编写一个排序算法，它有 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()