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

| 给定这种排序算法，您如何表达其时间复杂度？最初显示在这里（部分存档）。

#!/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

已邀请:

7 个回复

锑寝粒

O(max(input)+n) 由于大多数排序算法都无法识别数据，因此很难表达这种复杂性。它们的时间取决于数据量，而不是数据本身。如此处指出的那样，FWIW不是用于排序数据的可靠算法。

桑娠贯涤

似乎没有人解决的一个问题是如何实现这些“ 2”。最终，它们最终会出现在某个地方的调度程序中，并且操作复杂性将取决于所使用的调度算法。例如，如果将2作为事件放入优先级队列，则最终可能会得到与堆排序等效的结果，复杂度为O（n log n）。天真的调度算法可能会导致O（n ^ 2）。

磐去裸猜饲

我认为paxdiablo最接近，但不是出于正确的原因。时间复杂度忽略了实际硬件上的问题，例如高速缓存大小，内存限制，在这种情况下，进程数和调度程序的操作受到限制。基于Wikipedia页面的时间复杂度，我想说的答案是您无法确定运行时复杂度，因为如果将其定义为：通常通过对算法执行的基本运算的数量进行计数来估算时间复杂度，其中基本运算需要固定的时间来执行。因此，算法花费的时间量和执行的基本运算的数量最多相差一个常数。那么我们就不能谈论该算法的运行时间复杂性，因为基本运算所花费的时间差异很大，以至于所花费的时间相差一个常数以上。

阀傻

该算法的时间复杂度和过程复杂度均为O(braindead)：在数据集中具有足够大的值的情况下，您将一直等待答案，直到太阳爆炸（264秒才是半个万亿年之久）。如果数据集大小足够大，您将（a）达到流程限制；（b）发现早睡会在后者开始之前完成，这意味着set5ѭ不会正确地对sort6ѭ和2进行排序。在这种情况下，时间复杂度无关紧要。您无法获得比“错误”更小的优化。可以使用复杂度分析来比较算法，以随着数据集大小的变化而进行比较，但是当算法最初是荒唐的时候就不行了:-)

弦砂牧扁

我使用Jordan，但我认为挂钟时间复杂度最好用O（2 ^ m）表示，其中m是每个项目的大小，而不是O（max（input））。如果每个项目的大小为m，则最大项目的整数值为2 ^ m（减1，但是没有人关心）。通过构造，该算法要求建立时间小于1（恒定）。因此，挂钟时间复杂度O（2 ^ m），操作计数复杂度O（n）。考虑到建立时间的改进算法可能具有挂钟时间复杂度O（2 ^ m + n）。例如，它可以在开始时记下当前时间，计算base_time = start_time + k*len(list)（对于某个适当的常数k），然后让线程休眠直到时间base_time+i。然后k*len(list)显然是O（n），i显然是O（2 ^ m），总共是O（2 ^ m + n）。

吠强祷豪硅

如果您阅读了该主题，将会看到您的问题已得到解答。时间复杂度为O(max(input))，操作复杂度（操作数）为O(n)。

磨标烫徽啪

虽然看起来像线性，但我认为复杂度仍然是O（log（n）* max（input））。当我们讨论渐近时间复杂度时，它意味着n无限大时要花费多少时间。基于比较的排序算法不能快于O（n * log（n）），并且Sleep-Sort实际上是基于比较的：进程休眠n秒然后唤醒。操作系统需要从所有睡眠过程中找到最少的剩余睡眠时间，并在需要时间的情况下将其唤醒。这将需要一个优先级队列，该队列需要O（logN）的时间来插入元素，并且O（1）会找到最小的元素，而O（logN）会删除最小的元素。当n变得非常大时，将花费超过1秒的时间来唤醒进程，这使其大于O（n）。

要回复问题请先登录或注册

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

7 个回复

发起人

time_complexity

问题状态

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

与内容相关的链接

7 个回复

发起人

time_complexity

问题状态