wom*_*omp 168 sorting algorithm big-o
我的同事们带我回到了我的大学时代,今天早上讨论了排序算法.我们回忆起我们最喜欢的StupidSort,我们其中一个人确信我们已经看到了一种排序算法O(n!).这让我开始寻找可以找到的"最差"排序算法.
我们假设一个完全随机的排序会非常糟糕(即随机化元素 - 它是否按顺序排列？没有？再次随机化),我环顾四周,发现它显然叫做BogoSort,或者是Monkey Sort,或者有时只是随机排序.
Monkey Sort似乎具有最差的表现O(?),最好的表现O(n)和平均表现O(n·n!).
是否存在任何比平均性能更差的命名算法O(n·n!)？或者只是比一般的猴子排序更愚蠢？
Bio*_*eek 431
来自David Morgan-Mar的Esoteric Algorithms页面:Intelligent Design Sort
介绍
智能设计排序是一种基于智能设计理论的排序算法.
算法描述
原始输入列表按其精确顺序排列的概率为1 /(n!).这样的可能性很小,说这是偶然发生的,这显然是荒谬的,因此它必须由智能分拣机有意识地按顺序排列.因此,可以安全地假设它已经以某种方式进行了最佳排序,超越了我们对"升序"的幼稚理解.任何改变该顺序以符合我们自己的先入之见的尝试实际上会使它更少排序.
分析
该算法在时间上是恒定的,并且就地对列表进行排序,根本不需要额外的存储器.事实上,它甚至不需要任何可疑的技术计算机的东西.赞美分拣机!
反馈
加里罗杰斯写道:
使排序不变的时间会否定分拣机的力量.分拣机存在于时间之外,因此排序是永恒的.要求时间来验证排序会降低分拣机的作用.因此...这种特殊的类型是有缺陷的,不能归因于'分拣机'.
异端!
Kei*_*son 291
很多年前,我发明了MiracleSort(但从未实际实现过).
Start with an array in memory.
loop:
Check to see whether it's sorted.
Yes? We're done.
No? Wait a while and check again.
end loop
最终,在存储芯片中翻转位的α粒子应该导致成功的排序.
为了获得更高的可靠性,请将阵列复制到屏蔽位置,并根据原始阵列检查可能已排序的阵列.
那么如何根据原始数据检查可能排序的数组呢？您只需对每个数组进行排序并检查它们是否匹配.MiracleSort是用于此步骤的明显算法.
编辑:严格来说,这不是算法,因为它不能保证终止."不是算法"是否有资格成为"更糟糕的算法"？
Bio*_*eek 130
一种排序算法,假设量子力学的多世界解释是正确的:
在算法结束时,列表将在唯一的宇宙中排序.该算法采用最坏情况O(N)和平均情况O(1)时间.事实上,进行比较的平均数是2:有50%的机会,宇宙将在第二元件上被破坏,有25%的机会,它会在第三个被破坏,等等.
Kw4*_*w4s 59
我很惊讶没有人提到过sleepsort ......或者我没注意到它？无论如何:
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
示例用法:
./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7
在性能方面它很糟糕(尤其是第二个例子).等待近3.5个月来排序2个数字有点糟糕.
Dan*_*iel 49
我有一位讲师曾经建议生成一个随机数组,检查它是否已经排序,然后检查数据是否与要排序的数组相同.
最好的情况O(N)(第一次宝贝!)最坏情况O(从不)
Yuv*_*dam 30
如果您以任何方式保持算法有意义,O(n!)那么您可以实现最差的上限.
由于检查要排序的集合的排列的每种可能性将采取n!步骤,因此您不能比这更糟糕.
如果你正在做更多的步骤,那么算法没有实际用途.更不用说以下简单的排序算法O(infinity):
list = someList
while (list not sorted):
doNothing
Der*_*urk 19
您应该对Pessimal算法和单纯性分析的激动人心的领域进行一些研究.这些作者研究了用最小的最佳情况开发排序的问题(你的bogosort最好的情况是Omega(n),而slowsort(参见论文)有一个非多项式的最佳情况时间复杂度).
小智 17
Bogobogosort.是的,这是一件事.到Bogobogosort,你是Bogosort的第一个元素.检查是否有一个元素已排序.作为一个元素,它将是.然后你添加第二个元素,并将这两个元素Bogosort直到它被排序.然后再添加一个元素,然后再添加Bogosort.继续添加元素和Bogosorting,直到最终完成每个元素.在宇宙热死之前,这个设计永远不会成功.
小智 16
有一种叫做bogobogosort的东西.首先,它检查前两个元素,并对它们进行bogosorts.接下来,它检查前3个,bogosorts他们,等等.如果列表在任何时候出现故障,它会通过再次对前2个进行bogosort重新启动.常规bogosort的平均复杂度为O(N!),此算法的平均复杂度为O(N!1!2!3!... N!)编辑:为了让您了解此数字的大小,对于20个元素,该算法平均需要3.930093*10 ^ 158年,远高于提出的10 ^ 100年的宇宙热死(如果它发生),而合并排序需要大约.0000004秒,冒泡排序.0000016秒和博格索需要308年,139天,19小时,35分钟,22.306秒,假设一年是365.242天,计算机每秒执行250,000,000次32位整数运算.编辑2:这个算法并不像"算法"奇迹排序那么慢,这可能就像这样,在成功排序20个元素之前,会让计算机陷入黑洞,但如果确实如此,我会估计平均复杂度2 ^(32(32位整数中的位数)N)(元素数)(数量<= 10 ^ 40年,因为重力加速了筹码运动,并且有2 ^ N个状态,即2 ^ 640*10 ^ 40,或约5.783*10 ^ 216.762162762年,虽然如果列表开始排序,其复杂性只会是O(N),比合并排序更快,这只是N log N甚至在最糟糕的情况下.Edit3:这个算法实际上比奇迹排序慢,因为大小变得非常大,比如1000,因为我的算法的运行时间为2.83*10 ^ 1175546年,而奇迹排序算法会运行时间为1.156*10 ^ 9657年.
Set*_*eth 15
这是我在大学里找到室友的两种方式
1)检查订单2)可能发生奇迹,转到1
和
1)检查它是否有序,如果不是2)将每个元素放入数据包并将其从远程服务器反弹回自己.其中一些数据包将以不同的顺序返回,因此请转到1
Ice*_*unk 14
总是有Bogobogosort(Bogoception!).它在列表的越来越大的子集上执行Bogosort,然后如果列表未被排序则重新开始.
for (int n=1; n<sizeof(list); ++n) {
while (!isInOrder(list, 0, n)) {
shuffle(list, 0, n);
}
if (!isInOrder(list, 0, n+1)) { n=0; }
}
Pat*_*her 10
1将您的物品分类到索引卡片上
2在距离您家一英里的刮风天将它们扔到空中.
2将它们扔进篝火并确认它们被完全摧毁.
3检查您的厨房地板是否正确订购.
4如果订单不正确,请重复此操作.
最佳案例场景是O(∞)
根据KennyTM的敏锐观察进行上述编辑.
它不仅可以实现任何可以想象的短于无穷大的O(x)值,所以所花费的时间是可证明的(如果你可以等那么久).
没有什么比无限更糟糕了.
Bozo sort是一种相关算法,用于检查列表是否已排序,如果不是,则随机交换两个项目.它具有相同的最佳和最差情况表现,但我会直观地预期平均情况比Bogosort更长.很难找到(或产生)有关该算法性能的任何数据.
π的段
假设π包含所有可能的有限数组合.请参阅math.stackexchange问题