睡眠排序的时间复杂度是多少？
给定这个排序算法，你如何表达它的时间复杂度？
#!/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
Given this sort algorithm how do you express its time complexity?
Originally presented here (partial archive).
#!/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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
O(max(input)+n)这种复杂性似乎难以表达，因为大多数排序算法与数据无关。它们的时间随数据量变化，而不是数据本身。
FWIW，正如此处所指出的，这不是一种可靠的数据排序算法。
O(max(input)+n)The complexity just appears awkward to express because most sorting algorithms are data agnostic. Their time scales with the amount of data, not the data itself.
FWIW, as pointed out here, this is not a reliable algorithm for sorting data.
这取决于这些睡眠的实现方式。最终它们最终会出现在某个调度程序中，操作的复杂性将取决于所使用的调度算法。例如，如果将睡眠作为事件放入优先级队列中，您可能最终会得到相当于堆排序的结果，复杂度为 O(n log n)。简单的调度算法可能会导致O(n²)。
It depends on how those
sleeps are implemented. Ultimately they end up in a scheduler somewhere, and the operational complexity will depend on the scheduling algorithm used. For example, if thesleeps are put as events in a priority queue you will likely end up with something equivalent to heapsort, with complexity O(n log n). A naive scheduling algorithm might result in O(n²).我认为 paxdiablo 最接近，但理由不正确。时间复杂度忽略了实际硬件上的问题，例如缓存大小、内存限制以及在这种情况下的进程数量和调度程序的操作的有限性。
根据时间复杂度的维基百科页面我想说答案是你无法确定运行时复杂度，因为如果它定义为：
那么我们就不能谈论该算法的运行时复杂性，因为基本操作所花费的时间差异很大，以至于所花费的时间相差超过一个常数因子。
I think paxdiablo is nearest, but not for the right reason. Time complexity ignores issues on real hardware such as cache sizes, memory limits and in this case the limited number of processes and the operation of the scheduler.
Based on the Wikipedia page for Time complexity I'd say the answer is that you can't determine the runtime complexity because if it is defined as:
Then we can't talk about the runtime complexity of this algorithm because time which the elementary operations take is so vastly different, that the time taken would differ by more than a constant factor.
该算法的时间复杂度和过程复杂度都是
O(braindead)：(2,9,9,9,9,9,...,9,9,1)将无法正确排序1和2。在这种情况下，时间复杂度是无关紧要的。您不可能得到比“错误”更差的优化。随着数据集大小的变化，可以使用复杂性分析来比较算法，但当算法一开始就很荒谬时就不行了:-)
Both the time complexity and the process complexity of that algorithm are
O(braindead):(2,9,9,9,9,9,...,9,9,1)will not sort the1and2correctly.Time complexity is irrelevant in this case. You can't get any less optimised than "wrong". It's okay to use complexity analysis to compare algorithms as the data set size changes, but not when the algorithms are ludicrous in the first place :-)
我同意 Jordan，但我认为挂钟时间复杂度最好表示为 O(2^m)，其中 m 是每个项目的大小，而不是 O(max(input))。
如果每个项目的大小为 m，则最大的项目将具有整数值 2^m（减一，但没人关心这一点）。通过构造，该算法要求建立时间小于 1（一个常数）。
因此，挂钟时间复杂度为 O(2^m)，操作计数复杂度为 O(n)。
考虑到设置时间的修改算法可能具有挂钟时间复杂度 O(2^m + n)。例如，它可以在开始时记下当前时间，计算
base_time = start_time + k*len(list)（对于一些适当的常数k），然后让线程休眠直到时间base_time +我。那么k*len(list)显然是 O(n)，而i和以前一样是 O(2^m)，总共是 O(2^m+n) ）。I'm with Jordan, except that I think the wall-clock-time complexity is better expressed as O(2^m) where m is the size of each item, rather than O(max(input)).
If each item has size m, the largest item will have the integer value 2^m (minus one, but nobody cares about that). By construction, the algorithm requires the set-up time to be smaller than 1, a constant.
So wall-clock-time complexity O(2^m), operation-count complexity O(n).
A modified algorithm taking into account set-up time would likely have wall-clock-time complexity O(2^m + n). For instance, it could note the current time at the beginning, calculate
base_time = start_time + k*len(list)(for some appropriate constant k), then have the threads sleep until timebase_time+i. Thenk*len(list)is clearly O(n) andiis O(2^m) as before, for a total of O(2^m+n).如果您阅读该主题，您会发现您的问题已经得到解答。时间复杂度为
O(max(input))，操作复杂度（操作次数）为O(n)。If you read the thread you'll see that your question is already answered. The time complexity is
O(max(input))and the operational complexity (number of operations) isO(n).虽然看起来像线性的，但我认为复杂度仍然是 O(log(n) * max(input))。
当我们谈论渐近时间复杂度时，它指的是当n无限大时需要多少时间。
基于比较的排序算法不可能比 O(n * log(n)) 更快，而睡眠排序实际上是基于比较的：
进程睡眠 n 秒并唤醒。操作系统需要从所有休眠进程中找到剩余休眠时间最少的进程，如果到了时间就唤醒该进程。
这将需要一个优先级队列，插入一个元素需要 O(logN) 时间，找到最小元素需要 O(1) 时间，删除最小元素需要 O(logN) 时间。
当n变得很大时，唤醒一个进程需要1秒以上的时间，这使得它大于O(n)。
Though looks like linear, I think the complexity is still O(log(n) * max(input)).
When we talk about asymptotic time complexity, it means how much time is taken when n grows infinitely large.
A comparasion-based sorting algorithm cannot be faster than O(n * log(n)), and the Sleep-Sort, is actually comparasion-based:
The processes sleep n seconds and wake. The OS need to find the least remaining sleeping time from all the sleeping process, and wake the one up if it's about time.
This will need a priority queue, which takes O(logN) time inserting an element, and O(1) finding the minimum element, and O(logN) removing the minimum element.
When n gets very large, it will take more than 1 second to wake up a process, which makes it larger than O(n).
O(max(n, max_i))，其中 n 是要排序的项目数，max_i 是输入数组中任何项目的最大值。但排序算法实际上效率不高。
O(max(n, max_i)), where n is the number of items to sort and max_i is the max value of any item in the input array. But sort algorithm not efficient practically.