資料結構-時間複雜度 - 考試

※ 引述《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))

獻醜了

--