スリープソートの時間複雑性は？

質問

このソートアルゴリズムが与えられたとき、その時間複雑性はどのように表現されますか？

<ストライク 元々はここで発表された (一部アーカイブ) .

#!/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 が最も近いと思いますが、正しい理由ではありません。時間の複雑さは、キャッシュ サイズ、メモリの制限、そしてこの場合はプロセス数の制限とスケジューラーの動作など、実際のハードウェア上の問題を無視します。

に基づくと ウィキペディアの「時間の複雑さ」のページ と定義されていれば、実行時の複雑さは判断できない、というのが答えになりますね。

時間の複雑さは、一般的にアルゴリズムによって実行される初歩的な操作の数を数えることによって推定され、初歩的な操作は実行に一定の時間を必要とします。したがって、かかる時間の量とアルゴリズムによって実行される初歩的な操作の数は、最大でも定数ファクターによって異なっています。

では、初歩的な操作にかかる時間があまりにも大きく異なるため、このアルゴリズムの実行時の複雑さについて話すことはできませんので、かかる時間は定数倍以上異なることになります。