[理工] 资料结构_p.36 试题6 fmtshk PTT批踢踢实业坊

[理工] 资料结构_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

看懂了，谢谢

继续阅读

离散重复取组合应用问题zxc2179vbnm [理工] 电力系统问题olikatw 离散 p.3-17 范例三zxc2179vbnm [理工]资料结构p.1-34,复杂度计算fmtshk [理工] 请教一题电磁学考古题nick65415 离散第二章 104题zxc2179vbnm [理工] 离散环 9-101一题请益mistel [理工] 资料结构 heaptriumphant10 [理工] 线代—特征值transform157 [理工] 离散树的基本定义与性质sososlee