很明显，啃算法导论是我必须要做的事情，参考《算法导论》b站，和《算法导论》英文版

算法导论分为两个部分，第一部分为算法分析，第二部分为算法设计。

算法分析关注性能，也就是时间复杂度。

第一章   算法分析

T（n）表示是期望运行时间，是关于输入规模n的函数。

我们需要一个有关输入的统计分布假设，不然期望运行时间无从谈起。常见情况就是均匀分布，就是输入是每种输入n都是等可能出现的。

那么最好情况输入（欺骗）

1.1 渐进分析技术（伟大的算法分析技术）

忽略常量，不去真正比较时间，而是关注T(n）与n的增长趋势。

关注三个符号，就是上界、中界、下界？

例子1

插入排序的最坏情况下，计算其运行次数，使用渐进分析就是

 

O（n2），使用一点点算术级数的小技巧就可以，这里的O是一种描述符号。

例子2

然后又是合并排序

两个列表合并排序的时间复杂度仅仅是O（n）的，是线性的。那么对于合并排序，可以有一个递归表达式

就会得到分析的递推树，问题是树有logn那么高、树的叶子节点就是n个。自然就可以得到O（nlogn）复杂度。

那么就可以得到归并排序比插入排序快的结论。

 

 

第二节课   渐进符号、递归和解法（数学角度）

1 定义

1.1    基于O（）符号的数学严格定义，待写

会有O（）的不对称，还有其数学形式化定义，还有其误差分析，O表示上界。

 

1.2 

  现在是下界的数学严格定义了，（可能也是最好情况的时间复杂度分析），待写

 

 

2 应用

2.1 解递归式

   有三种方法，代换法和

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

，