睡眠排序的时间复杂度是多少? [英] What is the time complexity of the sleep sort?

问题描述

给定这种排序算法，你如何表达它的时间复杂度?

Given this sort algorithm how do you express its time complexity?

最初出现在这里 (部分存档).

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

推荐答案

我认为 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:

时间复杂度通常通过计算算法执行的基本操作的数量来估计，其中基本操作需要固定的时间来执行.因此，算法所用的时间量和执行的基本运算次数最多相差一个常数因子.

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

那么我们不能谈论这个算法的运行时复杂度，因为基本操作所花费的时间差别很大，所花费的时间相差不止一个常数.

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.

这篇关于睡眠排序的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！