我为娱乐写了一个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]

解决方案

回答

克里斯和我在另一个问题中提到了Bozosort和Bogosort。

回答

我能想到的一种方法是通过一个函数来计算每个元素的发布位置，该函数逐渐将大元素移到末尾，将小元素移到末尾。如果使用基于触发的函数，则可以使元素在列表中振荡，而不是直接朝其最终位置移动。在处理完集合中的每个元素之后，请进行完整遍历以确定数组是否已排序。

我不太肯定这会给你O(n！)，但它应该仍然很慢。

回答

总会有NeverSort，它是O()：

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

回答

我认为，如果我们进行大量复制，则可以得到"合理的"蛮力搜索(N！)，每种情况下花费N ^ 2次，得出N！* N ^ 2

回答

有一种(已证明！)最差的排序算法，称为慢排序，该算法使用乘和降范式并在指数时间内运行。

虽然算法较慢，但它不会稳定地进行，而是执行随机跳转。此外，慢速排序的最佳情况仍然是指数，而不变。

回答

如何遍历所有n个整数t的所有数组(n个整数元组是可数的，所以这是可行的，尽管这当然是无限循环)，对于每个数组：

• 如果它的元素恰好是输入数组的元素(请参见下面的算法！)，并且对该数组进行了排序(例如，线性算法，但我敢肯定我们会做得更糟)，则返回t;
• 否则继续循环。

要检查长度为n的两个数组a和b是否包含相同的元素，如何使用以下递归算法：循环遍历0和n-1之间的所有索引对(i，j)，并且对每个这样的对

• 测试a [i] == b [j]：
• 如果是，则仅当通过从a中删除a [i]和从b中删除b [j]获得的列表的递归调用返回TRUE时，才返回TRUE；否则，返回TRUE。
• 继续循环一对，如果所有一对都完成了，则返回FALSE。

时间将很大程度上取决于输入数组中整数的分布。

认真地讲，这样的问题有道理吗？

编辑：

@Jon，随机排序平均将为O(n！)(由于存在n！个排列，因此我们找到正确的排序的概率为1 / n！)。这适用于不同整数的数组，如果某些元素在输入数组中多次出现，则可能会略有不同，然后取决于输入数组的元素分布(以整数为单位)。

回答

我们总是可以进行随机排序。它通过随机重新排列所有元素，然后检查是否已排序来工作。如果没有，它将随机地求助于它们。我不知道它如何适合big-O表示法，但肯定会很慢！

回答

这是我们可以获得的最慢的有限排序：

将Quicksort的每个操作链接到Busy Beaver功能。

到我们进行> 4次运算时，我们将需要向上箭头表示法:)