Bogosort的平均时间复杂度是多少？

我听说Bogosort的行为没有上限。不过，我从来没有听到有人谈论它的平均行为。这是一个愚蠢的任务，但不切实际的思想实验仍然是一种很好的做法，尽管它们可能不切实际。Bogosort的平均时间复杂度是多少？

我想说的是，每学期是：

P(x==y)*P(x!=y)^(k-1) 
    = 1/n * (1-1/n)^(k-1) 
    = (n-1)^(k-1)/n^k

其中k为0和更大。我知道这个系列是收敛的，所以我们可以找到一个有限到有限的复杂关系（不像最坏的情况，其他人试图写成O（无穷大），因为试图在无限功能）

任何人都可以解决这个问题吗？或者，这是一种复杂性，如果没有无限的总和，就不可能写出或近似？

来源

2013-11-09 John P

它就在维基百科页面上...... – delnan

你是对的，当然，我不认为会有一个广泛的页面，或者我只是谷歌搜索它。 –

有一个更直接的方法来做到这一点。 Bogosort通过随机排列元素来工作，并在结果排列排序时终止。有n！数组元素的可能排列（假设它们都是不同的），并且只有其中一个排序。因此，输入的均匀随机置换排序的概率为1/n！。使用标准的概率结果，这意味着，根据预期，在我们生成排序的排列之前将发生的排列的数量是n !.这意味着Bogosort的预期运行时间为Θ（n＆middot; n！），因为我们执行n！随机排列，每个排序需要花费时间Θ（n）做（和Θ（n）检查时间）。

如果你想在这个题目正式的数学论述，认为在看文章Sorting the Slow Way，其中分析BOGO排序等相关种类。

希望这会有所帮助！

来源

2013-11-10 05:09:34 templatetypedef

平均需要O（1）次才能确定随机排列没有排序。虽然排列本身仍然是O（n），但如果你做了一个Fisher Yates，你可以在第一个反演出现在第k步时尽早放弃排列。这又让你在O（1）处产生并拒绝一个部分的，没有排序的排列。 –

@ rrenaud-这是一个很好的观点。我假设我们并没有试图优化bogosort，因为它是bogosort。 :-) – templatetypedef

Bogosort的平均时间复杂度是多少？

回答

相关问题