2,708
次編輯
「《演算法導論》筆記」修訂間的差異
無編輯摘要
Tankianting（討論 | 貢獻） （→Ch 3） |
Tankianting（討論 | 貢獻） |
||
| 行 111： | 行 111： | ||
還有一些函數的定義（中學數學等） | 還有一些函數的定義（中學數學等） | ||
== Ch4 分治法 == | |||
分治法是用遞迴的方法來解決一個問題。 | |||
* 基本情境：只需直接處理不用遞迴 | |||
* 遞迴情況下執行： | |||
** 分解 | |||
** 處理 | |||
** 合併 | |||
buttom out： * 不需繼續遞迴即可以解決 * 分拆分治法的遞迴式 | |||
'''遞迴式''' * 基本情況：fib(0) = 1 * 遞迴情況：fib(n) = fib(n-1)+fib(n-2) | |||
n_0 = 閾常數，如果： | |||
* n < n_0 => T(n) = θ (1) | |||
* n >= n_0 => 於有限的遞迴次數終止 | |||
=>T(n)是演算法相關的(algorithmic) | |||
[[category:資訊]] | [[category:資訊]] | ||