1

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

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

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

4

7 回答 7

4

[编辑：]没有有限状态的确定性过程需要“O（infinity）”，因为最慢的过程是通过所有可能的状态。这包括排序。

[较早，更具体的答案：] 不。对于大小为 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

假设您的意思是 theta 表示法（紧密绑定）......

如果您施加额外的限制，即算法是智能的（当它找到排序排列时返回）并且必须在有限的时间内访问列表的每个排列，那么答案是否定的。列表只有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 回答