[理工] 分析時間複雜度...

[pythoner (pythoner)]

最近要考演算法，想請問一下，在還沒教 Master Theory 的情況

能不能用 Master Theory 去證 Binary Serach 跟 Quick Sort ...

題目是寫 Show that the average case 為 O(...)

不想寫那很恐怖的證明，想直接用 Master Theory，有沒有可能要不到分 ...

(不過很明擺著就是要考那一常串很恐怖的證明 ...)

還是乖乖的回去看證明 QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.107.172.39
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510576351.A.06B.html
※ 編輯: pythoner (120.107.172.39), 11/13/2017 20:33:52
推 TMDTMD2487: 問你們教授，啊用的話記得要寫a,b,f(x)用master theor
→ TMDTMD2487: em跟case幾，我被教授扣過這個分
問教授教授就把考試題目上規定啦 (那幾個證明是每年幾乎必考)

是想問問看直接用 master theorem 的合理性 ...

謝謝
※ 編輯: pythoner (120.107.172.39), 11/13/2017 20:38:44
→ TMDTMD2487: 要證明的就用證的ㄅ
→ ken52011219: 要用Master theorem 請把 master theorem 的證明證
→ ken52011219: 出來 不然都不會拿到完整分數
推 alan23273850: 就算版上大大說可以，教授還是有權力扣分吧
推 sarsman: 問學長了解一下教授的個性比較保險
→ TMDTMD2487: 用master看得出來的題目，應該蠻好證的吧……
推 shownlin: ken大說把mt證出來再套...那一張考卷都要滿了吧...
→ ken52011219: 對QQ  我遇到的教授們對這點都很堅持  因此我都不用m
→ ken52011219: aster theorem 除非是選擇題