睡眠排序的時間複雜度是多少？

鑑於這種排序算法，你如何表達它的時間複雜度？睡眠排序的時間複雜度是多少？

~~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

來源

2011-06-24 justinhj

我認爲這是一個問題，不管現實世界的實際性如何 – justinhj

+20

絕對是一個很好的學術問題。如果它激起思想，就像它爲我所做的那樣，那麼它就必須具有價值。 –

我希望我可以編輯我的評論，閱讀「一個有趣的問題」，這就是我的意思，oops – justinhj

我覺得paxdiablo是最近的，但不正確的原因。時間複雜度忽略了實際硬件上的問題，例如高速緩存大小，內存限制以及在這種情況下進程的有限數量和調度程序的操作。

基礎上Wikipedia page for Time complexity我想說的答案是，你不能確定，因爲如果它被定義的運行復雜性：

時間複雜度通常通過計算進行基本操作的數量估計通過該算法，基本操作需要固定的時間量來執行。因此，算法所花費的時間量和基本操作的數量最多相差一個常數。

那麼我們就不能談論這個算法的運行時複雜度，因爲基本操作所花費的時間差別很大，所花費的時間會相差超過一個常數因子。

來源

2011-06-25 05:00:08 justinhj

O(max(input)+n)

的複雜性只是出現尷尬的表達，因爲大多數排序算法是無關的數據。它們的時間與數據量有關，而不是數據本身。

FWIW，正如here所指出的那樣，這不是用於排序數據的可靠算法。

來源

2011-06-24 22:23:58 blahdiblah

我認爲它需要是O（最大（輸入）+ n）其中是輸入量。如果遍歷所有輸入需要的時間比處理最大輸入需要的時間更長，那麼O（max（輸入））將是不正確的？ – yarian

您可以通過標準化數據來降低複雜性。將所有輸入除以最大（輸入）。 – keyboardr

這給你一個掛鐘時間的大O界限（儘管它應該是'O（n log（n））'來考慮調度器的工作）。但與大多數排序算法不同的是，這種算法在一段時間內會使CPU空閒，所以CPU時間的複雜度爲'O（n）'來迭代並啓動睡眠線程/進程，再加上'O（n log n）調度程序中的CPU時間來管理下次喚醒隊列。即** O（n log n）'CPU時間是吞吐量成本，但是'O（max（input）+ n log（n））'掛鐘時間是延遲成本。** –

如果您閱讀主題，您會看到您的問題已經得到解答。時間複雜度爲O(max(input))，操作複雜度（操作次數）爲O(n)。

來源

2011-06-24 22:25:45

線程肯定有答案，但我不知道它是否正確 – justinhj

該算法的時間複雜度和流程複雜度都是O(braindead)。

在數據集中有足夠大的值值，您將等待答案，直到太陽爆炸。

具有足夠大的數據集大小，你會

（1）打你的進程限制;和
（2）發現早睡者會在後者開始前完成，這意味着設置(2,9,9,9,9,9,...,9,9,1)將不會正確排序1和2。

在這種情況下時間複雜性是無關緊要的。你不能獲得比「錯誤」更少的優化。

沒關係使用複雜的分析算法比較的數據集大小的變化，而不是在算法首先是可笑的:-)

來源

2011-06-24 22:44:16 paxdiablo

要使其保持正常工作，您需要放大睡眠時間，以便連續數字之間的最小時間差大於時間排隊所有的睡眠。假設內核中有效的喚醒隊列算法，這可能是'O（n log n）'。我認爲這仍然歸結爲'O（n log n）'CPU時間，可能極其糟糕的掛鐘時間。 –

似乎沒有人提到過的一點是如何實現這些sleep。最終他們最終進入某個調度器，而操作的複雜性將取決於所使用的調度算法。例如，如果sleep s作爲事件放在優先級隊列中，則最終可能會得到相當於堆排序的內容，其複雜度爲O（n log n）。天真的調度算法可能會導致O（n^2）。

來源

2011-07-11 21:55:12 hammar

雖然看起來像線性，但我認爲複雜度仍然是O（log（n）* max（input））。

當我們談論漸近時間複雜度時，意味着當n增長無限大時需要多少時間。

基於比較討論排序算法不能大於爲O（n *的log（n）），和睡眠排序更快，實際上是比較討論基於：

的處理睡n秒和喚醒。操作系統需要從所有睡眠過程中找到最少的睡眠時間，如果時間到了，就要喚醒睡眠時間。

這將需要一個優先級隊列，它需要O（logN）時間插入一個元素，並且O（1）找到最小元素，並且O（logN）移除最小元素。

當n變得非常大時，喚醒進程需要1秒以上的時間，這使得它大於O（n）。

來源

2013-03-19 07:30:50 RnMss

我和喬丹在一起，除了我認爲掛鐘 - 時間複雜度更好地表示爲O（2^m），其中m是每個項目的大小，而不是O（max（輸入））。

如果每個項目的大小爲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）。

來源

2013-06-09 02:16:15 sabik

睡眠排序的時間複雜度是多少？

回答

相關問題