📌 📄 内容摘要:
onewhite 在 【时间复杂度】算法时间复杂度计算 中发帖
先不上具体的算法，先来理论一下如何去计算一个算法的时间复杂度。
这里给出一个递归关系的表达式，你能够得出具体的复杂度是多少吗？
f(n)=\begin{cases} 1 & n = 1 \\ n + 4f(n/2) & n > 1 \end{cases}
a. f(n) \in \Theta(n^2) ✓
b. f(n) \in \Theta(n)
c. f(n) \in \Theta(n \log n)
有三种方法可以去算出来
瞪眼法
你直接猜，别管这个那个的，直接就随便猜一个，然后看答案就完事了
Master theorem
很可惜的是，第一种方法的损失太大了。在一个错一道就扣一个正确的情况下，第一种方法还是太难去成功了。那么这里介绍第二种方法，经典的Master theorem。
Master theorem中定义到，
T(n)=hT( n/b ) + g(n...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/504948/1
─────────────────────────────
📢 来源：LINUX DO
