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

看板Grad-ProbAsk作者 (J.K.Lee)時間6年前 (2017/10/18 17:28), 6年前編輯推噓7(7推 0噓 8→)
留言15則, 6人參與, 6年前最新討論串1/1
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
推
10/18 18:35, 6年前 , 1F
logb a 如果a小於一算出來就是負的 變成n^-xx，也
10/18 18:35, 1F
→
10/18 18:35, 6年前 , 2F
就是n的倒數，只要n越大複雜度反而變低了不合理，
10/18 18:35, 2F
→
10/18 18:35, 6年前 , 3F
不知道是不是因為這樣
10/18 18:35, 3F
推
10/18 22:50, 6年前 , 4F
a > 0 不就是跟 a >= 1 等價嗎? 你質疑的點是?
10/18 22:50, 4F
master theorem 沒有限制a是整數
推
10/19 08:43, 6年前 , 5F
a 可以是實數 我想 a > 0 應該也是可以證明的
10/19 08:43, 5F
我的証明過程只用到 a>0，所以我無法理解M.T.有什麼數學上的理由要限制a>=1
→
10/19 08:44, 6年前 , 6F
畢竟 Akra–Bazzi method 沒有這個限制
10/19 08:44, 6F
推
10/20 20:33, 6年前 , 7F
遞迴樹權重會越來越小，就沒討論的必要了吧?
10/20 20:33, 7F
推
10/21 08:03, 6年前 , 8F
要看 b 的大小吧 所以要確認 regularity condition
10/21 08:03, 8F
推
10/25 01:16, 6年前 , 9F
有哦...master theorem 有限制a是integer greater than
10/25 01:16, 9F
→
10/25 01:16, 6年前 , 10F
or equal to 1
10/25 01:16, 10F
原來有限制是整數。
→
10/25 01:16, 6年前 , 11F
k大其實是正解
10/25 01:16, 11F
※ 編輯: JKLee (111.248.76.116), 10/27/2017 09:28:18
推
10/30 13:20, 6年前 , 12F
a的個數是指子問題（subfunction)的個數，可以想像
10/30 13:20, 12F
→
10/30 13:20, 6年前 , 13F
為一棵子樹，應該沒有非整數的個數吧，會有非整數
10/30 13:20, 13F
→
10/30 13:20, 6年前 , 14F
的東西應該是data個數而不是subfunction的個數詳細
10/30 13:20, 14F
→
10/30 13:20, 6年前 , 15F
概念看一下演算法楓葉本對MT的證明就會清楚了
10/30 13:20, 15F
‣ 更多 JKLee 的文章
文章代碼(AID): #1Pvnw_lJ (Grad-ProbAsk)