[理工] 资结时间复杂度 easion0317 PTT批踢踢实业坊

楼主: easion0317 (仲夏萤火虫) 2015-06-24 21:52:38

http://i.imgur.com/iHZ6v3V.jpg
题目在图上求big oh
递回怎么去假设出式子再求时间复杂度

作者: goldflower (金色小黄花) 2015-06-24 23:22:00

你从n往下展应该会比较清楚

作者: harryron9 (两个世界) 2015-06-25 09:30:00

某方面来讲你已经写完了T(n)=2*T(n/2)+2*T(n/2)=4T(n/2)=16T(n/4)...

楼主: easion0317 (仲夏萤火虫) 2015-06-25 21:20:00

http://i.imgur.com/bE9XmtR.jpg看不是很懂详解的式子我的式子列的跟h大一样

作者: goldflower (金色小黄花) 2015-06-25 22:47:00

喔喔他是用master method做的直接代入就好n^log2(2)=n > 常数所以T(n)=theta(n)

楼主: easion0317 (仲夏萤火虫) 2015-06-26 11:41:00

这题我是分析一个母问题切割成两个子问题可是MM的公式T(n)=aT(n/b)+f(n)这种形式才可使用这题怎么用MM去看

作者: goldflower (金色小黄花) 2015-06-26 21:30:00

因为他写recursive部分的theta(1)那边那个是指乘法和加法的部分这个是是为常数而且是每层递增所以符合f(n)的条件

继续阅读