关于递归式复杂度求解的一些想法。
虽然说具体数学有一整章讲渐进式，但鉴于学这个性价比太低了，基本也用不到，所以很多有关渐进式的东西会在本文总结。
接下来进入正题。
为什么不直接用主定理？
这是本文十分重要的一个点。这里先贴一下主定理，为了使文章尽可能简洁，就不贴出证明了：
主定理的适用范围是非常广的，但是它对下面这个式子束手无策：
发现主定理用不了，因为子问题里的 \(\sqrt n = \frac{n}{\sqrt n}\) 得到 \(b\) 并不是一个常数，此时主定理就（萎了）用不了了。
你以为我接下来要说怎么做了，但我还要继续乳主定理（），看到下面这个递归式
这个式子的子问题并不是平均划分的，因此也就不能用主定理。
好事成三，我们再看一个式子：
此时该式子不符合主定理的三种情况，也是不能用主定理的，但是这个式子可以用Akra-Bazzi定理，读者可自行学习。
（虽然但是主定理在一般情况下还是非常好用的啦）
暴力
对于不能用主定理解决的递归式，《算法导论》中推荐使用递归树+数学归纳法解决，但是这样工作量过于巨大了，会显得很蠢，还不如乱猜再证明来的快，此时就十分的难受，不知道怎么整。
为了让我们能更简洁与优美的暴力，采用更好的方法是必要的。我们尝试在递归树的基础上进行优化。就像记忆化搜索可以优化深度优先搜索一样，我们可以对每一个可能出现的子问题考虑它对答案的贡献。
拿 \((1)\) 式举例，我们无需列出一整棵递归树，只需对每个子问题统计贡献即可。用 \(w(x)\) 表示子问题 \(T(x)\) 的贡献，就可以有下面的表：
| \(x\) | \(w(x)\) |
|---|---|
| \(n\) | \(n\) |
| \(\sqrt n\) | \(4\sqrt n \times \sqrt n = 4n\) |
| \(\sqrt {\sqrt n}\) | \((4\sqrt {\sqrt n})(4\sqrt n )(\sqrt {\sqrt n}) = 16n\) |
相信对数字敏感的人无需列表即可感性地证明规律，即使不太敏感，表的前三项也足够找到规律：
那么设 \(n=2^k\) 那么层数就应该是：
总的复杂度就会是：
而\(\sum\limits_{i=0}^{\log_2 \log_2n}4^i \sim 4^{\log_2 \log_2n}\)
所以答案为
不够劲？不妨再来一组。我们来解决式 \((2)\) ，而这甚至表都可以不列出来。不难发现层数最为 \(\log_2n\) ，而层贡献为 \(层值 \times 层出现次数\) ，假设当前层为 \(n\frac 1{2^k}\) ，相当于一次能走一步、两步或三步，走 \(k\) 步的方案数， \(OGF\) 搞起，但是没搞出来（？），反正就这么整就成。