我的同事今天早上讨论了排序算法，让我回到了大学时代。 我们回想起我们最喜欢的像StupidSort ，我们中的一个确信我们已经看到了一个O(n!)的排序算法。 这让我开始寻找可以找到的“最差”排序算法。
我们假设一个完全随机的排序将是非常糟糕的（即随机化的元素 - 它是按顺序吗？不，随机再次），我环顾四周，发现它显然被称为BogoSort，或猴子排序，或有时只是随机排序 。
猴子排序似乎具有O(∞)的最坏情况表现， O(∞) O(n)的最佳情况表现，以及O(n·n!)的平均性能。
有没有任何具有比O(n·n!)更差的平均性能的命名算法？ 还是比猴子排序一般？
My co-workers took me back in time to my University days with a discussion of sorting algorithms this morning. We reminisced about our favorites like StupidSort, and one of us was sure we had seen a sort algorithm that was O(n!). That got me started looking around for the "worst" sorting algorithms I could find.
We postulated that a completely random sort would be pretty bad (i.e. randomize the elements - is it in order? no? randomize again), and I looked around and found out that it's apparently called BogoSort, or Monkey Sort, or sometimes just Random Sort.
Monkey Sort appears to have a worst case performance of O(∞), a best case performance of O(n), and an average performance of O(n·n!).
Are there any named algorithms that have worse average performance than O(n·n!)? Or are just sillier than Monkey Sort in general?
最满意答案
来自David Morgan-Mar的 “神秘算法”页面： 智能设计排序
介绍
智能设计排序是基于智能设计理论的排序算法。
算法描述
原始输入列表的准确顺序为1 /（n！）。 这样做的可能性很小，这显然是荒谬的，这是偶然发生的，所以一个聪明的分拣机必须有意识地按照这个顺序。 因此，可以放心地认为，它已经被最优化地排除在某种程度上超越了我们对“升序”的天真的凡人的理解。 任何尝试改变该顺序以符合我们自己的先入之见，实际上会使其排序较少。
分析
该算法在时间上是恒定的，并且对原位进行排序，完全不需要额外的内存。 事实上，它甚至不需要任何可疑的技术电脑的东西。 赞美分拣机！
反馈
加里·罗杰斯写道：
使时间不定时否定分拣机的力量。 分拣机存在于时间之外，因此排序是永恒的。 要求时间验证排序可以减轻分类器的作用。 因此...这种特殊的种类是有缺陷的，不能归因于“分拣机”。
异端！
From David Morgan-Mar's Esoteric Algorithms page: Intelligent Design Sort
Introduction
Intelligent design sort is a sorting algorithm based on the theory of intelligent design.
Algorithm Description
The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.
Analysis
This algorithm is constant in time, and sorts the list in-place, requiring no additional memory at all. In fact, it doesn't even require any of that suspicious technological computer stuff. Praise the Sorter!
Feedback
Gary Rogers writes:
Making the sort constant in time denies the power of The Sorter. The Sorter exists outside of time, thus the sort is timeless. To require time to validate the sort dimishes the role of the Sorter. Thus... this particular sort is flawed, and can not be attributed to 'The Sorter'.
Heresy!
更多推荐
发布评论