我怎么写比O更糟糕的那种(n!)

Question

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

Answer 1

有一种(经过验证的!)最差的排序算法称为慢排序,它使用"乘法和投降"范式,并以指数时间运行.

虽然您的算法速度较慢,但​​它不会稳定地进行,而是执行随机跳转.此外,慢速排序的最佳情况仍然是指数,而你的是恒定的.

Answer 2

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