※ 引述《mqazz1 (无法显示)》之铭言： : 我看Cormen的书....在导median of median的时间复杂度被困住了 : 3( 1/2 * n/5 - 2 ) ≧ 3n/10 - 6 : T(n) ≦ T(n/5) + T(7n/10 + 6) + O(n) : ≦ c(n/5) + c + c(7n/10) + 6c + an : ＝ 9cn/10 + 7c + an : ＝ cn + (-cn/10 + 7c + an) : which is at most cn if : -cn/10 + 7c + an ≦ 0 整理: -c( n/10 - 7) + an ≦ 0 an ≦ c( (n-70)/10 ) 再乘过去就是下式了 : c ≧ 10a(n/(n-70)) when n>70 : ↑这个式子我不知道是怎麽计算出来的.. : ------------------------------------------------------------------ : 然後为什麽最後选择 c ≧ 20 就可以满足这个不等式呢? 因为n大於等於140(详见递回式) 故n/(n-70) ≦2 故c ≧ 10a(n/(n-70))可写成 c ≧ 10a(2) =20a 所以应该是20a 而不是20 --- 题外话 看你问的这几个问题 感觉你是要考研究所 或是要准备学校期中考? 如果是的话不用算的这麽详细啦 算time complexity的题目把递回式子写出来最重要 剩下就粗略算给他看就好了 -- 「我是谁」 「其实我也是，我只记得自己把皮夹克的袖子部分剪掉了。」 「我是谁? 好像确实是保护地球和平的什麽人来着。」 ˍˍ 「说起来的确似曾相识，我好像一直以来都在追逐你。」 ▕攘夷▏ 「可能我们以前就是这样融合摇滚和RAP来保护世界的吧?」 ▕JｏY▏ ￣￣ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.116.6.166