設(shè)計(jì)并行算法的思路(2) parallel mergesort

Sequential Mergesort

func mergesort(A) |A| = n
   if n <= 1 return A
   (spawn)
   A1 = mergesort(A[1:n/2])
   A2 = mergesort(A[n/2+1:n])   
   (sync)
  return merge(A1,A2)

T(n) = 2T(\frac{n}{2}) + O(n) = O(nlogn)

W_{pms} = 2W_{pms}(\frac{n}{2}) + O(n)

D_{pms}(n) = D_{mps}(\frac{n}{2}) + O(n)= O(n)

  1. work optimality(right)
  2. polylog span(no)

那么應(yīng)該如何提高效率呢？

我們可以看見這個(gè)算法的主要限制是merge的過程是順序的，所以限制了算法的速度。那么有什么方式可以提高效率呢？

image

其實(shí)我們可以用在 A 序列中找到一個(gè)終點(diǎn)，并用它將 B 分成兩部分使得 a_{1} ,b_{1} \leq a_{m}\leq a_{2},b_{2}

那么在最理想的情況下我們可以得到 D_{pm}(n) = D_{pm}(\frac{n}{2})+O_{pm}(logn_) ,其中 log n 是二分查找 B的重點(diǎn)的過程。

在最壞的情況下，是 \frac{n_A}{2} 與 n_B merge的

\left \lfloor{\frac{n_{A}}{2}}\right \rfloor + n_{B} \leq \frac{n_A}{2} + n_B

= \frac{n_A+n_B}{2} + \frac{n_B}{2}

= \frac{n}{2} + \frac{n_B}{2} \leq \frac{n}{2} + \frac{n}{4} = \frac{3n}{4}

D_{pm}(n) = D_{pm}(\frac{3n}{4})+O_{pm}(logn_) = O(log^2n)

D_{pms}(n) = D_{mps}(\frac{n}{2}) + O(log^2n)= O(log^3n)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 小時(shí)候，每到夏天，父親單位都會(huì)發(fā)"褔?yán)?quot;茶，通常是兩大紙包，聞起來香香的那種，大概是我們今天所說的茉莉花茶。...
    東緒閱讀 335評(píng)論 0贊 0
  • 鐘表 可以回到起點(diǎn) 卻已不是昨天 日歷 撕下一頁(yè) 非常的簡(jiǎn)單 但要把握住一天 卻很難 緣分 雖有萬(wàn)萬(wàn)千 卻要順其自...
    琢玉書生閱讀 253評(píng)論 0贊 4
  • 熟悉的工作，可以問問自己： 1. 這個(gè)工作，做得真的無(wú)可挑剔了嗎？ 2. 我的工作方式，可以改變嗎？ 3. 有沒有...
    孤遠(yuǎn)閱讀 172評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容