作者bobobola ( )
看板Examination
标题Re: [问题]资料结构-时间复杂度
时间Sun Mar 24 23:21:28 2013
※ 引述《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
1F：推 GLTY:简单易懂~ 03/24 23:41