Re: [問題]資料結構-時間複雜度
※ 引述《smalldulan (媽媽咪阿)》之銘言：
: 最近在看王致強老師的資料結構中的遞迴部分，
: 其中的組合公式用非遞迴來改寫，
: 他時間複雜度是θ(m(n-m))，
: 不過我算到θ((m+1)(n-m+1))化簡成θ(m(n-m)+n)
: 就卡住了~不太懂要怎麼化簡成書中的複雜度呢？
: 小弟資質愚鈍，想請教各位高手怎麼得到書中的複雜度？
θ((m+1)(n-m+1))=θ(mn-m^2+m+n-m+1)=θ(mn-m^2+n+1)
因為時間複雜度只要知道它的最高層級是什麼就夠了 不用很精準的算出執行次數
m與n皆為變數 且無法得知誰的冪次較高 於是時間複雜度可將較低層級捨去
留下最高層級
於是就變成θ(mn-m^2)=θ(m(n-m))
獻醜了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.35.166.245
推
03/24 23:41, , 1F
03/24 23:41, 1F
討論串 (同標題文章)