楼主:
JKLee (J.K.Lee)
2018-03-12 14:52:12Master Theorem 假设 T(n) = a*T(n/b) + f(n).
我这里令 E = log_b a.
下图表示出 f(n) 与 T(n) 之间的复杂度关系。
https://i.imgur.com/y21Kv4o.png
在 f(n) 的复杂度介于 n^(E-ε) 与 n^(E+ε) 之间时 (图中红虚线)，
M.T.可以处理的例子很有限。
我希望复杂度在这个范围内的所有 f(n)，依然可以代公式来求 T(n)。
以下是我得到的结果。