master theorem解題 在 コバにゃんチャンネル Youtube 的最佳解答
「master theorem解題」的推薦目錄：
- 關於master theorem解題 在 コバにゃんチャンネル Youtube 的最佳解答
- 關於master theorem解題 在 大象中醫 Youtube 的最佳貼文
- 關於master theorem解題 在 大象中醫 Youtube 的精選貼文
- 關於master theorem解題 在 Re: [理工] [DS]-時間複雜度- 看板Grad-ProbAsk - 批踢踢實業坊 的評價
- 關於master theorem解題 在 master theorem教學2022-在Facebook/IG/Youtube上的焦點 ... 的評價
- 關於master theorem解題 在 master theorem教學2022-在Facebook/IG/Youtube上的焦點 ... 的評價
- 關於master theorem解題 在 20/01/05 - 合併排序法- 演算法的分析與證明 的評價
- 關於master theorem解題 在 調皮豹-楊過的刑法小天地 :: 讀書心得分享網站 的評價
- 關於master theorem解題 在 發展解題能力數學工作坊| 四年級的等值分數該怎麼教 - Facebook 的評價
- 關於master theorem解題 在 blog-mirror/index.html at master · morris821028/blog ... - GitHub 的評價
master theorem解題 在 master theorem教學2022-在Facebook/IG/Youtube上的焦點 ... 的推薦與評價
master theorem教學2022-在Facebook/IG/Youtube上的焦點新聞和熱門話題資訊，找master theorem ... master theorem解題-臉書推薦/討論/評價在PTT、Dcard、IG整理一次看 ... ... <看更多>
master theorem解題 在 master theorem教學2022-在Facebook/IG/Youtube上的焦點 ... 的推薦與評價
master theorem教學2022-在Facebook/IG/Youtube上的焦點新聞和熱門話題資訊，找master theorem ... master theorem解題-臉書推薦/討論/評價在PTT、Dcard、IG整理一次看 ... ... <看更多>
master theorem解題 在 Re: [理工] [DS]-時間複雜度- 看板Grad-ProbAsk - 批踢踢實業坊 的推薦與評價
※ 引述《doom8199 (～口卡口卡 修～)》之銘言：
: ※ 引述《yesa315 (XD)》之銘言：
: : T(n) = 3T(n/4) + nlog n 使用Θ表示
: : 2
: : 這有比較快速的算法嗎? 例如代換法??
: : 用暴力法求解我也求不太出來 有請高手給個方向
: : 謝謝!
: ---
: 令 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: with f(n) = a*nlogn + b*n + c*logn + d
: → T(n) = 3T(n/4) + 3f(n/4) - f(n)
: = 3T(n/4) + (-a/4)nlogn - (3a/2 + b/4)n + 2c*logn + (2d-6c)
: 與原式比較係數後可得:
: ┌ (-a/4) = 1 ┌ a = -4
: │ 3a/2 + b/4 = 0 → │ b = 24
: │ 2c = 0 │ c = 0
: └ 2d-6c = 0 └ d = 0
: 所以 f(n) = -4nlogn + 24n ____(1)
: 因此 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: = 3^[log_4 (n)] * [T(1) + f(1)]
: = n^(log√3) * [T(1) + f(1)]
: → T(n) = T(1)*n^(log√3) + f(1)*n^(log√3) - f(n)
: = T(1)*n^(log√3) + 24*n^(log√3) + 4nlogn - 24n
: or T(n) = Θ{ nlogn }
[挖以前的文章]
如果要純解題的話，你可以套下面這個方法，當然也是從 Master 定理整理出來的：
要訣就是在比大小就對了…大的就贏了 >////<
給題目： T(n) = aT(n/b) + f(n)
log a
b
Step 1：計算 n
Step 2：比較一下 Step 1 與 f(n) 值誰的複雜度大
則 T(n) = Θ(複雜度大的那個)
Step 3：Step 1 的值與 f(n) 的複雜度相同的話
則 T(n) = Θ( f(n) * lgn)
(多乘一個 lgn)
Step 4：處理一下例外情形，就是當 f(n) 比 Step 1 的值少 lgn 倍時。
不能使用 Master Theorem。
也就是說看到 f(n) 有 lgn 時就要小心一下就對了。
For Example
---------------------------------------------------------------------
T(n) = 3T(n/4) + nlog n
2
log 3
4
n < n log n
2
所以 T(n) = Θ(大的那個) = Θ(nlog n)
2
---------------------------------------------------------------------
T(n)=T(n/2)+O(1)
log 1
2
n = n^0 = 1 跟 f(n) 一樣
所以 T(n) = O(1) * lgn = Θ(lgn)
---------------------------------------------------------------------
T(n)=4T(n/2)+n
log 4
2
n = n^2 > n = f(n)
所以 T(n) = Θ(大的那個) = Θ(n^2)
---------------------------------------------------------------------
T(n) = 3T(n/4) + n
log 3
4
n < n = f(n)
所以 T(n) = Θ(大的那個) = Θ(n)
---------------------------------------------------------------------
T(n) = 2T(n/2) + n / lg n
log 2
2
n = n > n / lgn = f(n)
這時發現 f(n) 少了 lgn 倍，所以就不能套 Master Theorem了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.5.68
感謝，修正了 XD
... <看更多>
相關內容