睡眠排序的时间复杂度是多少？

Question

鉴于此排序算法,您如何表达其时间复杂度？

最初在这里介绍 (部分档案).

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

Answer 1

O(max(input)+n)

由于大多数排序算法都是数据不可知的,因此复杂性似乎很难表达.它们的时间与数据量成比例,而不是数据本身.

FWIW,如指出这里,这不是对数据进行排序可靠的算法.

Answer 2

似乎没有人解决的一点是如何sleep实施.最终,它们最终会出现在某个调度程序中,操作复杂性将取决于所使用的调度算法.例如,如果将sleeps作为事件放在优先级队列中,您可能会得到等同于heapsort的东西,其复杂度为O(n log n).天真的调度算法可能导致O(n ^ 2).

Answer 3

我认为paxdiablo距离最近,但不是正确的原因.时间复杂性忽略了真实硬件上的问题,例如高速缓存大小,内存限制以及在这种情况下有限数量的进程和调度程序的操作.

基于时间复杂度的维基百科页面我会说答案是你无法确定运行时的复杂性,因为如果定义为:

通常通过计算算法执行的基本操作的数量来估计时间复杂度,其中基本操作花费固定的时间量来执行.因此,算法所花费的时间量和基本操作的数量最多相差恒定因子.

然后我们不能谈论这个算法的运行时复杂性,因为基本操作所花费的时间是如此巨大的不同,所花费的时间将不同于一个常数因子.

Answer 4

时间复杂度和该算法的过程复杂性都是O(braindead).

如果数据集中的值足够大,您将等待一个答案,直到太阳爆炸.

有了足够大的数据集大小,你就可以了

• (1)达到你的工艺限制; 和
• (2)发现,早睡觉将完成后面的一些开始之前,这意味着该组(2,9,9,9,9,9,...,9,9,1)不会进行排序1和2正确.

在这种情况下,时间复杂度无关紧要.你不能得到任何不如"错误"的优化.

当数据集大小发生变化时,可以使用复杂性分析来比较算法,但是当算法首先是荒谬的时候就不行了:-)