给定一个函数sorted，如果列表已排序且运行时间复杂度为 O(n)，则该函数返回 True，您将如何描述这种排序的运行时间:
def sort(l):
while not sorted(l): random.shuffle(l)
假设洗牌是完全随机的。
这会用大 O 符号写吗？或者是否有其他方法可以对具有随机成分的算法进行分类？
最佳答案
这个算法叫做 Bogosort .它是一类名为 Las Vegas Algorithms 的算法的实例。 .拉斯维加斯算法是 Randomized Algorithms它总是保证正确的结果，但不保证计算资源。
Bogosort 的时间复杂度不能直接用Bachmann-Landau Notation 表示，因为它的概率性质。但是，我们可以对其 expected 发表声明时间复杂度。 Bogosort 的预期时间复杂度为 O(n·n!)。
关于algorithm - 随机排序运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/288966/