随机排序的运行时间

Question

sorted如果列表按O(n)运行排序,给定一个函数返回True ,你会如何描述这种运行时间:

def sort(l):
    while not sorted(l): random.shuffle(l)

假设洗牌是完全随机的.

这会用big-O表示法写吗？或者是否有其他方法使用随机组件对算法进行分类？

Answer 1

信不信由你,这里有一个wiki条目:http: //en.wikipedia.org/wiki/Bogosort

平均情况:O(N*N!)

Answer 2

该算法称为Bogosort.它是一类称为拉斯维加斯算法的算法实例.拉斯维加斯算法是随机算法,它始终保证正确的结果,但不保证计算资源.

由于其概率性质,Bogosort的时间复杂性无法直接用巴赫曼 - 兰道表示法表达.但是,我们可以对其预期的时间复杂性做出陈述.Bogosort的预期时间复杂度是O(n·n!).