[理工] 演算法 Master Theorem 的常數範圍

[JKLee (J.K.Lee)]

Master Theorem 假設

T(n) = a*T(n/b) + f(n)

其中a>=1，b>1


我自己在推導M.T.的過程中只用到 a>0，

但是我看到的資料都是假設 a >= 1，Why?

目前看到的理由是: a是代表子問題的個數，所以a為正整數。

有什麼數學上的理由使得我們要假設 a >= 1 ?


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.161.200.52
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508318911.A.BD3.html
推 fatezero5262: logb a 如果a小於一算出來就是負的 變成n^-xx，也
→ fatezero5262: 就是n的倒數，只要n越大複雜度反而變低了不合理，
→ fatezero5262: 不知道是不是因為這樣
推 kyuudonut: a > 0 不就是跟 a >= 1 等價嗎? 你質疑的點是?
master theorem 沒有限制a是整數

推 FRAXIS: a 可以是實數 我想 a > 0 應該也是可以證明的
我的証明過程只用到 a>0，所以我無法理解M.T.有什麼數學上的理由要限制a>=1

→ FRAXIS: 畢竟 Akra–Bazzi method 沒有這個限制
推 awesomeXD: 遞迴樹權重會越來越小，就沒討論的必要了吧?
推 FRAXIS: 要看 b 的大小吧 所以要確認 regularity condition
推 shownlin: 有哦...master theorem 有限制a是integer greater than
→ shownlin:  or equal to 1
原來有限制是整數。

→ shownlin: k大其實是正解
※ 編輯: JKLee (111.248.76.116), 10/27/2017 09:28:18
推 windwaker112: a的個數是指子問題（subfunction)的個數，可以想像
→ windwaker112: 為一棵子樹，應該沒有非整數的個數吧，會有非整數
→ windwaker112: 的東西應該是data個數而不是subfunction的個數詳細
→ windwaker112: 概念看一下演算法楓葉本對MT的證明就會清楚了