随机排序的复杂性

Question

好吧，这可能是对包含 n 个不同整数的数组 arr 进行排序的最糟糕方法，但我想分析这个算法：

1. 检查 arr 是否已排序。如果是，return.
2. 随机排列arr的元素。
3. 重复步骤 1 和 2，直到出现 return。

Goofy 的分类程序是否有效？ GoofySort 的最佳案例是什么？最佳情况下的 运行 时间是多少？最坏的 运行 时间是多少？平均 运行 时间是多少？

Answer 1

这种排序称为Bogosort。

• 最好的情况是 O(n)：您的第一个随机 return 排序列表。如果任何大小合适的名单都发生这种情况，您可能应该买一张彩票。
• 平均情况是 O((n+1)!)
• 最坏的情况是无限的。不能保证随机改组会 return 排序列表。毕竟是随机的

Answer 2

你说的是 bogosort 算法..

回答您的问题：

What is a best case for GoofySort?

在最好的情况下，数组已经排序，或者第一次随机化排序。

What is the running time in the best case?

要么检查它是否排序所花费的时间，要么它洗牌所花费的时间，然后检查两次以进行排序。

What is the worst-case running time?

它是无限的。你可以永远随机播放 {1,3,2} => {3,1,2} => {1,3,2} => {3,1,2}。

What is the average case running time?

它是 O((n+1)!)（参见 wiki 文章）。