iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 10
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 10

Day 10: 平行計算模型(三) Parallel Computation Model, Part 3 -- 前綴極小值問題

今天跟大家聊個簡單的問題:前綴極小值問題。

https://ithelp.ithome.com.tw/upload/images/20181025/2011237654R2m4bevE.png

我們知道計算 min 可以在 O(n/p) 時間算得,但由於有 n 個值要輸出,一個顯然的平行算法可以在 O(n^2/p) 時間內被算出來。但絕大多數情形這個方法是沒有太大效率的,此時我們該怎麼辦呢?

注意到,我們並不太希望把輸出寫成 b[i] = min{b[i-1], a[i]},原因是因為這樣會造成 b[i] 的計算必須取決於 b[i-1] 的值,這樣會難以平行。

事實上,我們可以把 a[1..n] 拆成 p 段,每一段先分別找出該段的最小值。這麼一來就可以再次利用這 p 個最小值找出 b[1..(n/p)*x] 的最小值。然後又可以根據這個算出正確的 b[i] 值,整體時間複雜度為 O(n/p + p)(如果追求極致,第二步我們可以再次遞迴下去解決同樣的子問題,所以利用前天的找最大值方法,這樣的時間複雜度是 O(n/p + log p / log log p)。)但總之我們可以達到高度的平行化,也就是說時間複雜度大約是 O(n/p),比起原本的直接的演算法來說快了幾乎 p 倍。

https://ithelp.ithome.com.tw/upload/images/20181025/20112376tBVtc1X0vV.png

明天我們來看看這東西可以怎麼應用 :)

大家有興趣的話可以猜猜看XD


上一篇
Day 9: 平行計算模型(二) Parallel Computation Model, Part 2 -- 搜索問題
下一篇
Day 11: 平行計算模型(四) Parallel Computation Model, Part 4 -- 最長嚴格遞增子序列
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言