前言

本文是B站《算法导论》MIT公开课的随课笔记，关于内容和笔记格式有问题的朋友欢迎私信交流~

本节内容应该是上一节内容的延续，从数学的角度更严谨地探讨两件事情：①渐进符号介绍；②如何求解递归式

一. 渐进符号介绍

1. 渐进符号O

（1）数学定义

对于f(n) = O(g(n))，意味着存在c＞0，n0＞0，使得对于所有的n≥n0，都有0≤f(n)≤c·g(n)

e.g. 2·n² = O（n³）

解释：去掉首项系数（这里默认整个多项式已经降幂排列了）和低阶项，剩下的部分应该小于或等于n³。
【大O粗略地说就是小于等于】

（2）O符号的性质与理解

①不对称性：

对于f(n) = O(g(n))这个式子，等式两边并非对称的，这意味着并不存在以下两个式子
g(n) = O(f(n))
O(g(n)) = f(n)

②反映本质的想法——f(n)属于g(n)构成的函数集

• 把整个O(g(n))看做是满足一定条件的函数集
  
• 文字解释：O(g(n))是这样的一个函数集，内部的所有函数，都有与之对应的整数c和n0，使得f(n)这个函数以0和c·g(n)为界。
  
• 因为有了视作“集合”的观点，所以不能把渐进O看做是一个简单的等号，而应该看做是一个∈符号，这也解释了为什么O的关系是不对称的。

（3）渐进符号O的绝妙用法

①当做“宏”来使用

“宏”——位于公式中的一个集合，该集合被用于在某个特定的范围内表示匿名函数

E.g.1 f(n) = n³+O(n²)

• 这里表达了一个误差界限，表示f(n)这个函数主要由n³这个项组成，还包含一些关于n²的低阶项。

• <数学定义>：有一个函数f(n)，还有一个函数h(n)，h(n)是O(n²)的元素，使得f(n) = n³+h(n)。总的来说就是有这么一个低阶项h(n)，它是以常数倍的n²作为上界的。[这里f的等于号是数学意义上严格的等于号]

• 更含糊地说，可以说明f(n)是三阶的。

E.g.2 n²+O(n) = O(n²)

• <数学定义>对于任意的f(n)∈O(n)，都会存在相应的h(n)∈O(n²)，从而有n²+f(n) = h(n)
• 这里等号也是不对称的，具体的含义上文已经说明过了，理解成“∈”就很好解释了。
• 这个等式可以作为一个链条从前向后传递，从而得到新的渐进上界。

理解：大O符号，虽然在算法设计这门课中给了一个新的定义，但是乍一看，多看几眼，还是很像高等数学中学过的高阶无穷符号。

用这个思想去类比上面的等式，也是可以说的通的。

2. 渐进符号Ω

引入Ω的原因：很多时候，我们可能会更加关注一个算法的上界，因此我们前文探讨了很多O符号的渐进思想。

但在有些时候，我们同样也需要探讨算法的下界，比如在之后讲排序，我们会听到诸如“某些算法至少需要nlogn”的时间，因此我们引出了Ω符号。

另，笔者提醒，在学习Ω渐进符号的时候，就可以类比O符号来进行学习了。包括学习的思路以及框架。

（1）数学定义

上面是O渐进符号和Ω渐进符号的定义式的类比，直观看起来，就是把f(n)和g(n)的不等关系进行了调换。

e.g. sqrt(n) = Ω(lgn)

解释：对于充分大的n，根号n至少是lgn的常数倍。
【Ω基本上对应大于或者等于】

3. 渐进符号θ

（1）定义
θ（g(n)） = O(g(n)) ∩ Ω(g(n))

e.g. n² = θ(n²)

理解：对于一个最高阶为2次的多项式，忽略掉其相应的低阶项，那么的确和二次式是齐平的。

（2）性质

θ符号有点类似于=关系，但又不是完全严格的定义。

从集合的观点来看，θ符号对应的集合是O符号和Ω符号对应集合的交集。

4. 严格渐进符号小o和小ω

小o和小ω可以分别对应于小于符号和大于符号。

对照前文大O和大Ω的定义，有些许的变化：

①对于f(n) = o(g(n))，意味着对于任意常数c＞0，都存在一个常数n0＞0，使得对于所有的n≥n0，都有0≤f(n)≤c·g(n)

②对于f(n) = ω(g(n))，意味着对于任意常数c＞0，都存在一个常数n0＞0，使得对于所有的n≥n0，都有0≤g(n)≤c·f(n)

【conclusion】

二.递归式求解

1. 代换法

（1）代换法的步骤
①猜出解的形式，就是通过问题的定义大概推测出阶次和函数形式

②通过数学归纳法的定义来验证这个通解是否满足数学定义

③通过第②步的验证，同时也可以得到常数项

p.s.我们只需要猜测出解的形式，这一步是完全可以行的。因为通过前面的渐进符号，我们也知道，我们在关注算法规模的时候，常常是忽略常数项和系数项的。

（2）示例

①问题描述

②证明-O(n³)

说明：在推导过程中不能使用大O符号——

a.意味着，我们需要按照大O的定义，将数的渐进关系展开成不等关系。

b.因为当大O序列是一个延伸的无穷序列的时候，诸如O(f1) = O(f2)=…=O(fn)，即使这样的链式存在的，但此时第一项和最后一项之间的大O关系实质是不存在的。
p.s.见下面的例子

首先根据常识，可以知道上述需要证明的n = O(1)是一个伪命题，因为线性级别和常数级别还是有本质差异的。

但是根据数学归纳法的证明过程最终却可以证明出这个伪命题为真。

关键原因在于每一步进行O(1)渐进的时候，常数项都是不一样的，所以不能够这样使用。

“每次做这样的事情的时候，如果是有穷数量的常数加倍，没有大问题，仍然是常数；但是进行n次加倍的时候就不对了”，因为常数是依赖于变化的。

③证明-O(n²)

最后要满足归纳式，只需要n≥1即可，但是为了能可以满足Base条件（即T(1)的约束），还需要c1>>c2.

p.s.这部分不再赘述啦，如果看上面的推导式理解不了的可以戳进去视频35分40秒处有说明[这一处的前一个例子同样也讲到]

2. 递归树法

递归树法对于递归问题的求解总是很有效，而且能够给出一个直观印象，让我们大概知道题目的解是多少。

但是递归树法并非是严谨的解题方法，我们往往需要通过递归树法找到答案，再通过代换法进行求解。

（1）问题描述

T(n) = T(n/2) + T(n/4) + n²

对于这样一个递归式，可以理解为对于一个规模为n的问题，先四等分地递归，再二等分地递归，最后再处理一个复杂度为n²的非递归的工作。

（2）递归树绘制

借助递归树，就是以树的形式将递归式展开，再将所有项进行相加。

递归树展开和构成的基本原理：
根据递归式，将非递归项写在根节点中，再将递归项展开在其子节点上，之后递归地对子节点进行上述规则的展开。

根据上述步骤，可以得到递归树的形式如下图所示（直接截的课程视频内的图，高糊）
展开到最底层我们会得到一系列叶节点，达到常数级别。

对于展开的递归树来说，求叶节点的数目是一大难点。
且在本例中，每一棵子树的左右子树都是不均衡的，即缩减成常数的速度不一致。

可以定性地分析出叶节点数目的上界——n
“最开始的问题大小为n，递归成一个n/4的问题和一个n/2的问题，直到递归成1为止”n/4+n/2 = 3n/4 ，显然要小于n

对于递归树的应用，不必要展开整个树的样子然后苦恼怎样求和，只需要针对每一层的非递归项一层一层进行求解即可。
第一层的非递归项即为n²，第二层的非递归项即为（5/16）n²，第三层的非递归项即为（25/256）n²，根据归纳的思想，我们可以看出每一层的非递归项的复杂度实质上就是一个等比级数。

（3）递归树求解

将每一层的复杂度进行相加（实质就是进行一个等比级数求和），可以放缩出来最后在大O的渐进思想下，问题规模是平方级别的。

这里想说一下关于等比级数求和放缩的问题，我们对于公比已知的等比级数是可以直接求解近似的。老师这里使用了一个很巧妙的近似思想。
对于一个常见的等比级数1+1/2+1/4+1/8+…=2，这个式子的理解可以借助于二进制，也就是等式左边一长串的求和式子可以写成二进制表示下的一个小数1.11111…1（无限个1），那么这个数字自然是逼近于2的。

而在本例中，等比是5/16，比1/2要小，所以最后得到的结果自然是要小于2的。
而且在这里的场景下，我们不需要关注最终的系数的具体数值是多少，只需要确定系数是一个常数即可。

3.主方法

主方法本质上可以看成是对递归树法的一个拓展，但它更加精确。
主方法是基于一个理论，称为【主定理】。
但主方法的限制较多，只能用于有限情况下的递归式。

（1）使用范围

主方法求解递归式时只适用于形如 T（n）= aT（n/b）+f（n）这样的递归式。
其中a≥1（保证至少递归一次），b＞1（必须保证子问题的规模是减小的，不然会进行无限次的递归），f(n)渐进趋正
【渐进趋正】：对足够大的n来说，f(n)是大于0的。

这意味着，使用主方法时每一个子问题的规模都应该保持一致，f(n)对应着非递归的问题规模

（2）主定理描述

主方法的核心思路就是将f(n)这一项和nlogb^a进行数值比较，从而得到不同的结论。