算法学习：解递归式以及渐进符号

事情变得有趣起来了，今天讲的是关于离散数学的内容，没有涉及纯粹的算法。
今天的课程内容属实是有点挑战性了，不管是能不能听下去还是理解成本。

今天的生活状态总体来说不太好，听完课就不太知道干啥了，
尤其是这样不涉及编程，不能支撑做题的，
课上的内容消化已经耗能较高，我就懒得做更多的探究。
在家里就容易活在固定模式里。
出去也找不到玩的，复读的同学好像也还没放假，找其他人有点胆怯，
总感觉离开家成本太大，在家里还得看妹妹。
玩游戏吧，开放世界或者沙盒的那种总感觉玩了特容易上瘾，而且后劲很大。
对于时间还是挺吝啬的，玩不开心，总是活在欲望与爆发希望之中。
感觉玩个游戏都有些功利化了，要是没有啥固定的结果就是个while(1)循环了一样。
家里的东西并不一定比那里好吃，特别是姥姥姥爷在家的时候（笑）。

要是想破局的话，学做饭、尽兴做事与玩游戏，并且敢于走出去，
我不确定自己能不能行动起来，不过写这篇也就是对我的一个提醒了。

今天是彻底地对于之前还挺模糊的渐进符号下了精确的数学定义，所以这一篇也要像人家老师说的，纯粹是数学的讨论（但也是思维的挑战）。

昨天见过了几种常用的渐进符号，也就是O, Ω, Θ, 实际上除此之外还有o，ω，分别与对应的大小关系构成“严格关系”（比如O表示小于等于，o表示严格小于）

对于这些符号，现在给出定义

1.O

我们用f(n) = O(g(n))形式来使用这个符号，
它的意义是，存在适当的c与n0，
使得对于所有的n >= n0, 满足0 <= f(n) <= c(g(n))

这里的O(g(n))符号表示的并不是另一个函数，而是一个集合，
所以这里的等于号就相当于一个属于符号∈
这里就如同一个原函数与原函数集的关系。

在昨天学习中已经接触到了这些符号都是有渐进的观点的，
也就是省去低阶项与系数，所以除去对于f(n)非负的假设
右边部分表示的是f(n) <= c(g(n)).
也即O表示小于等于的一个集合，这个小于等于包含很多含义。
有参数，阶次更低等等。

在表达式中，它可以与函数一起使用（如O(g(n)）
被用来替代一个抽象函数
如f(n) = n^3 + O(n ^ 2) 这个表达式表达一个“小于等于n^2的函数h(n)”
满足上面的函数关系。

那么已经有了上文的O的例子，其他符号理解起来也就简单一些了。

Ω相当于渐进上的”大于等于“，
o相当于渐进上的“小于”，ω相当于渐进上的“大于”。
Θ只有大写，之前写错了，相当于O与Ω的交集，
可以理解成渐进上的”相等“。
相当于给最高项加上系数或者加一个至几个低阶项。

前提是对于足够大的n，
因为当n为一个常数的时候，这些符号的n都是Θ(1)。
而f(n)需要大于等于0，后面如果有低阶项的话需要保证n足够大
（这里的大也不一定是更大，我想是大小的意思，需要一个合适的大小）.

接着就是严格的部分了。
解递归式

就和定积分一样，它没有固定的方法，
我们需要学习很多的方法，然后看看哪一种更适合

方法有三种
1.代换法
2.递归树法
3.主方法

主方法并不是主要的方法，只是用它是更为方便与固定的一条路。

一. 代换法

先听一下它的要求哈：

第一步，猜答案，而且必须猜对它，
（但是你可以不知道常数系数，但是它的形式必须对）

还是有点离谱哈，但是其实还行，给个例子就知道了。
实际上是根据自变量与函数值关系的变化来推，而且不需要管低阶项，

T(n) = 4 * T(n/2) + n
（先看看，过会再和你说是如何猜的）

我们一般是求上界，下界有时也会求。

假设我们猜想它是一个O(n^3)
那么自然T(k) <= k ^ 3 而且k < n

展开原式然后小于等于右边式子即可，推出C >= 1时，
O(n^3)是一个上界
实际上这里只是一个比较宽的上界，就好像说它是小于n的10次方也可以
但是不准确。

下面就是猜的方法了，

可以看出T(n)是T(n/2)的四倍，然后n是n/2的两倍，
是不是与n^2类似？
所以按照O(n^2)假设，类似做法一直改进假设即可。
想看解法，如下

但是这种方法往往太过于理论化（哈），我在面对这些式子的时候常常走神，写到一半就不知道自己的思路去哪里了，相比于第一种方法，第二种方法还是更直观一些。

二. 递归树法

所以又是我们昨天见过的，看起来挺复杂，听上去也挺吓人的递归树。
它有时是不太严谨的，但是它是万能的，
可以用它来猜正确答案，然后再用第一种方法来做。

出一个例子：
T(n) = T(n/4) + T(n/2) + n^2
（灵魂画手预警！！）

分支总数也就是分到最后Θ(1)的数量。–
虽然估测不出来，但是一定小于n
树高度就是这个递归树总共有几层。 – log2n
然后一层一层地找规律并求和。

第一层求和为 n^2
第二层求和为5/16n ^ 2
第三层求和为25/256n ^ 2

这样我们发现这个求和的结果是按照几何级数递减（小数等比）的，
所以我们就直接等比数列求和，或者也不用求和，
结果一定是与n^2有关的式子，而且系数一定是大于1小于2的。
就是O(n ^ 2)(这里有点存疑，我还得问问。)

3.主方法

它被称为“主”，是因为
它只能够被用到特定形式的递归式中 – 符合T(n) = aT(n/b) + f(n)
系数需要符合标准 – a必须>= 1 b>1
而且还得满足三种情况的其中一种（如下三种）。

对于每一种情况都有一个渐进的定理，
这些定理都可以使用递归树证明出来。

定理情况
比较f(n) 与 n^logba的相对大小

• 当f(n) = O(n^（logba - ε）），对于大于0的ε
  T(n) = Θ(n^logba)
• 2.当f(n) = Θ(n^logba*(log2n)^k) k>=0
  T(n) = Θ(n^logba * log2n^(k+1))
• 3.当f(n)比n^logba增长的快
  f(n) = Ω(n^(logba+ε)) ,对于大于0的ε
  而且f(n)要不断变小(af(n/b) <= (1 - ε’)f(n) ε’ > 0
  递归树的下一层要严格小于上一层
  T(n) = Θ(f(n))

这就是今天学习的递归树以及渐进符号内容，今天这样说来也收获了不少的东西呢！继续加油。