[理工] 资料结构_p.36 试题6

楼主: fmtshk (fmtshk)   2019-06-02 21:13:22
https://i.imgur.com/MfrL0J3.jpg
https://i.imgur.com/SGrJV8U.jpg
请问第三小题这段英文题目是什么意思呢?
"recursively processes two equal halves of a problem that each have an overhead
of O(n)?"
查翻译是“递回处理问题的两个想等的一半?”
有点不太懂@@
作者: skyHuan (Huan)   2019-06-02 21:37:00
每个问题递回处理变成两个size为一半的子问题
楼主: fmtshk (fmtshk)   2019-06-02 21:59:00
那再问一下(3)的答案旁写T(N)=2T(n/2)+theta(n)为何要多个theta(n)呢?
作者: skyHuan (Huan)   2019-06-02 22:12:00
最后说overhead是O(n),所以每步骤有theta(n)的cost
楼主: fmtshk (fmtshk)   2019-06-03 16:32:00
看懂了,谢谢

Links booklink

Contact Us: admin [ a t ] ucptt.com