2013-02-18 118 views
0

在本書http://www.scala-lang.org/docu/files/ScalaByExample.pdf的第2章,M. Odersky的寫了下面的實現快速排序階功能快速排序

def sort(xs: Array[Int]): Array[Int] = { 
if (xs.length <= 1) xs 
else { 
val pivot = xs(xs.length/2) 
    Array.concat(
    sort(xs filter (pivot >)), 
    xs filter (pivot ==), 
    sort(xs filter (pivot <))) 
} 
} 

,並說:「無論是勢在必行和功能實現具有相同的漸近 複雜 - O(N log(N))「 但是看起來不是,因爲我們對分區數組應用了兩次謂詞過濾。在經典命令版本中,我們使用一個循環來存儲數組。那麼功能實現O(N log(N))的運行時間是多少?

回答

2

快速排序且最多O(n)工作做得不超過O(log(n))越過數據很多其他的分而治之算法的工作。在每一步我們將數據分成大約一半,這意味着我們確實只有log2(n)通過數據(其中一個沒有被分割,一個被分成大約一半,等等)。

然後您只需檢查每次通過數據的時間不超過O(n)時間。過濾器是O(n),我們過濾三次;加concatO(n),我們做一次。因此我們做4*O(n)工作,這是O(n)

這不是最有效的算法,因爲所有的數據都通過相同的數據,但它是正確的順序。

4

filter本身具有O(n)和O(3n)= O(n),因爲3是一個常數因子。不管多大n,過濾器只會被調用3次。

編輯:過濾器被稱爲3倍