algorithm - 随机排序的运行时间

Question

sorted给定一个函数，如果在 O(n) 中运行的列表已排序，则返回 True的函数，你将如何描述这种排序的运行时间：

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

假设洗牌是完全随机的。

这会用大 O 表示法写吗？还是有其他方法可以对具有随机分量的算法进行分类？

Answer 1

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

Bogosort 的时间复杂度不能直接用Bachmann-Landau Notation 表示，因为它具有概率性质。但是，我们可以对其预期的时间复杂度进行说明。Bogosort 的预期时间复杂度为O(n·n!).

Answer 2

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

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

Answer 3

平均情况确实是 O(NN!)：

观察正好有 N! N个元素的排列。选择正确的概率正好是 1/N!。因此，根据大数的强定律，洗牌的预期数量是 N!。

另一个因素 N 来自哪里？您必须在每一步检查您选择的排列。这可以通过比较相邻元素来线性完成。因此有一个额外的因子 N。

上面的评论表明 O(g(n)) 表示法是“最坏情况”：

1) 那不是真的。O(g(n)) 的定义是：如果存在一些 c,d 使得 f(n) < c * g(n) + d 对于足够大的 n，f(n) 是 O(g(n)) . 没有什么关于“最坏情况”的。碰巧 g(n) 是一个比 f(n) 更大的函数，但纯数学定义没有说明“case”。

2）对于随机算法，无论如何做“最坏情况”分析是没有意义的。你可以想出一些非常糟糕的执行。

3) 真正糟糕的执行发生在一组度量 0 上（概率论者会说它们“几乎肯定”不会发生）。他们实际上是不可能观察到的。

Answer 4

Big-O 表示法假设最坏的情况。在最坏的情况下，这个算法永远不会终止。