Prune和Search的時間複雜度

我閱讀了很多關於Prune和Search算法的內容，我甚至詢問了一些內容以供確認。Prune和Search的時間複雜度

This是一個很好的來源。但是，有些事情我很難理解。像修剪的時間複雜度和搜索：

有人可以提供此簡要說明？

2013-07-16 KC-Chan

這是一個特定的修剪和搜索類型算法的時間複雜度。你應該在這個計算中描述算法和你不瞭解的內容。 – hivert

@hivert這可能是中位數的中位數算法。 –

@DavidEisenstat是的，找到中位數的那個。這有點混亂。 –

他們通過一些奇怪的方法解決了復發T（n）< = T（n/5）+ T（3n/4）+ Cn（C是大O常數）。對於缺少的基本案例和地板和天花板操作員，我們可以通過Akra–Bazzi或替代方法（本答案）解決。歸納假設是對於所有n'< n的T（n'）< = 20Cn'。然後

T(n) <= T(n/5) + T(3n/4) + Cn 
    <= 20C(n/5) + 20C(3n/4) + Cn 
     = 20C(4n/20) + 20C(15n/20) + Cn 
     = 4Cn + 15Cn + Cn 
     = 20Cn.

2013-07-16 12:27:47

回答