主定理

故事要从一道题说起^[1]：

在解决这个问题之前，我们恐怕需要先了解一下什么是主定理.

问题的定义

上面我们分析了若干个程序的时间复杂度，不难发现，有递归的程序的复杂度不是那么容易分析.

形式化地讲，递归的函数会形如：

在上面的式子中，表示我们问题的规模. 我们希望知道一个函数在此规模下的时间复杂度. 而这个函数会递归地将这个问题拆分成个同样需要函数解决的子问题，其中每个子问题的规模是，而且在这个拆分的过程中会额外需要一些步骤，它们的成本记作.

为了说明这个问题，我们先考虑一种简单的情况，抹掉，计算下面这个东西的复杂度：

首先思考，上面这个递归会进行多少层？

递归的核心思路就是：你希望解决一个大问题是吗？那就先解决一个小问题吧！ 当问题已经被分解至答案显而易见时，递归就可以退出了. 形式化地讲，每次递归，我们都会将规模的问题转化成规模的小问题，当规模达到（即常数），递归就可以结束了. 所以我们可以将式展开为：

其中，因为. 而且也应该是一个常数时间可以解决的问题，所以总的时间复杂度为：

为什么要变换形式呢？第一个不伦不类，换成n这样多项式的形式就顺眼多了

这样看来，对于形如式这样的递归问题，其复杂度应当是多项式的，而且阶为.

递归将大问题拆成小问题，but at what cost? 拆分问题是有代价的——为了拆分问题我们需要.那么会如何影响最终的复杂度呢？

这就引入了主定理，主定理的内容如下^[2]：

主定理

case1
如果存在，使得

那么

case2
如果存在，使得

那么

case3
如果存在，使得

同时存在常数以及充分大的满足

那么

课程之外，菜狗存而不论，数学定理，菜狗论而不证.

我们先略过证明，简单解释一下上面的情况.
事实上，我们讨论的就是的阶. 第一种情况，的上界是，这就是说的阶数小于，因此的时间复杂度就是. 而在第三种情况中，的下界是，这就是说的阶数大于，因此的时间复杂度取决于，为.

更加复杂的是：如果的阶数和等于呢？ 事实上，如果的阶数相同，我们还需要知道的阶数. 关于更详细的内容，请参看详细证明.

证明

未来再来探索吧

接下来我们回到一开始的那几道题，来体会一下主定理的强大：

Problem 4 (a)

解

因为. 因此由主定理可知：

Problem 4 (b)

解

因为. 因此存在，使得

所以

而且在这里可以任意小，所以事实上

Problem 4 (c)

解

因为. 所以可以找到使得

因为，所以由主定理可知：

Problem 4 (d)

解

因为. 所以由主定理可知