[理工] 演算法複雜度 gz9548171 PTT批踢踢實業坊

[理工] 演算法複雜度

作者: gz9548171 (瘋狂阿笨狗) 2019-03-25 15:54:11

https://i.imgur.com/0zTctmP.jpg
想請問一下第二題後面那串可以直接
看成n^2然後代master theorem嗎

作者: skyHuan (Huan) 2019-03-25 15:56:00

可以但題目應該是想要你用subtitution選擇題可以直接省略用master看，但證明用subtitution比較好

作者: gz9548171 (瘋狂阿笨狗) 2019-03-25 16:25:00

那想請問這題要怎麼用substitution 找thetaSubstitution只做過O的這題我試了n^2跟n^2+nlogn

作者: skyHuan (Huan) 2019-03-25 19:31:00

證O再用一樣的方法證Omega就是theta了

作者: gz9548171 (瘋狂阿笨狗) 2019-03-25 20:47:00

了解謝謝sky大

繼續閱讀

[理工] 計組第二章tank123zzz [理工]線代_p5-15_範例2fmtshk [理工] 線代課本（上）p.3-101 第2題boxunlu [理工] 計組第二章tank123zzz [理工] 線代_4-128範例6fmtshk [理工] 線性代數 3-52 向量空間請教mistel [理工] 108台大土木工數請教ucdrtz [理工] 108台大資工線代三題silenteve [理工] 台大資工在職遞迴求複雜度brucetu [理工] 線代 p.1-63 範例4raysun011081

Contact Us: admin [ a t ] ucptt.com