10

我为我的娱乐写了一个 O(n!) 排序，如果不完全替换它，就不能简单地优化它以更快地运行。[不，我不只是在物品被分类之前随机化这些物品]。

我如何编写更糟糕的 Big-O 排序，而不只是添加可以拉出以降低时间复杂度的无关垃圾？

http://en.wikipedia.org/wiki/Big_O_notation具有按增长顺序排序的各种时间复杂度。

编辑：我找到了代码，这是我的 O(n!) 确定性排序，带有有趣的 hack 以生成列表的所有组合的列表。我有一个稍微长一点的 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]
4

8 回答 8

9

有一种（已证明！）最差的排序算法，称为慢排序，它使用“乘法和降服”范式并在指数时间内运行。

虽然您的算法速度较慢，但​​它的进展并不稳定，而是执行随机跳跃。此外，慢排序的最佳情况仍然是指数的，而您的情况是恒定的。

于 2008-08-25T10:58:09.297 回答
3

Chris和我在另一个问题中提到了 Bozosort和Bogosort 。

于 2008-08-25T02:11:36.143 回答
2

总是存在 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
于 2008-08-25T03:00:59.100 回答
1

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

将 Quicksort 的每个操作链接到 Busy Beaver 函数。

当您获得 >4 次操作时，您将需要向上箭头符号 :)

于 2008-10-07T13:15:37.737 回答
1

你总是可以做一个随机排序。它的工作原理是随机重新排列所有元素，然后检查它是否已排序。如果没有，它会随机使用它们。我不知道它如何适合大 O 表示法，但它肯定会很慢！

于 2008-08-26T13:57:17.000 回答
0

How about looping over all arrays t of n integers (n-tuples of integers are countable, so this is doable though it's an infinite loop of course), and for each of these:

  • if its elements are exactly those of the input array (see algo below!) and the array is sorted (linear algo for example, but I'm sure we can do worse), then return t;
  • otherwise continue looping.

To check that two arrays a and b of length n contain the same elements, how about the following recursive algorithm: loop over all couples (i,j) of indices between 0 and n-1, and for each such couple

  • test if a[i]==b[j]:
  • if so, return TRUE if and only if a recursive call on the lists obtained by removing a[i] from a and b[j] from b returns TRUE;
  • continue looping over couples, and if all couples are done, return FALSE.

The time will depend a lot on the distribution of integers in the input array.

Seriously, though, is there a point to such a question?

Edit:

@Jon, your random sort would be in O(n!) on average (since there are n! permutations, you have probability 1/n! of finding the right one). This holds for arrays of distinct integers, might be slightly different if some elements have multiple occurences in the input array, and would then depend on the distribution of the elements of the input arrays (in the integers).

于 2008-08-26T13:33:58.990 回答
0

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

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

于 2008-08-25T02:18:43.413 回答
0

我认为，如果您进行大量复制，那么您可以获得“合理”的蛮力搜索（N！），每个案例需要 N^2 次，给出 N!*N^2

于 2008-08-25T03:23:09.280 回答