Algorithms 算法学习笔记20180414

今天我主要学习了算法中的一大块干货，序列求和与递归方程。因为许多实际的问题，都要用到循环迭代的方法，而这种方法所耗费的时间又比较大。因此也有许多理论知识点需要看。

先讲序列求和，我们以三种常见序列为基础进行介绍，一是等差数列，假设是最简单的自然数序列，公差为1，那么第1至n项的和为n(n+1)/2。二是等比数列，假设第1项为a，公比为q,则第n项为aq^k，则序列和为a(1-q^n+1)/(1-q)；三是调和级数，如1+1/2+1/3+1/4+...+1/n，其和近似为logn。

接着讲我们如何评价一个算法的时间复杂度。

首先要知道这个算法的时间复杂度的定义是什么，对于一个输入规格为n的问题，比如在一个长度为n的序列中查找x的位置。我们使用二分法查找，具体分三种情况讨论：

1）理想情况，x在序列中间位置，则查找一次即命中，使用时间记为常数时间c

2)  最差情况，x不在序列中，那它的值介于n个节点的所包含的区间内，共有n+1种可能

3）一般情况,x有序列中，但不是理想情况，当x在第1/4和3/4位置时，有2种可能，我们需要比较2次，以此类推，在1/8....7/8位置时，有8种可能，需要比较8次，规律是有t种可能位置时，有2^t-1次比较。

我们认为每一种可能性是等概率发生的，则要计算平均时间复杂度，

结果是(比较次数*比较时间)/(可能的输入情况）

我们还要考虑的一种情况是，当算法的精确和无法求出时，如何估计算法的时间复杂度。

这里分为5种情况，但主要是将T(n)放大或缩小，得到其紧确上界或下界。具体可参照这篇文章的介绍。

1.Θ表示渐近紧确界，即当n足够大时（n>n0)，f(n)的上下界与θ(g(n))渐近。

2.O表示渐近紧确上界，当n足够大时（n>=n0)，0<=f(n)<=g(n)

3.Ω表示渐近紧确下界,当n足够大时（n>=n0)，0<=cg(n)<=f(n)

4.o表示非渐近紧确上界，当n足够大时（n>=n0)，0<=f(n)<g(n)

5.ω表示非渐近紧确下界，当n足够大时（n>=n0)，0<=cg(n)<=f(n)

那递推方程的解怎么来算呢？主要有迭代方法，相消法和主定理方法三种。

迭代方法举例：

1. T(n)=2T(n-1)+1

           =2[2T(n-2)+1]+1

           =2^2T(n-2)+2+1=...=2^n-1+2^n-2+...+2+1

很明显这是一个等比数列，和为2^n-1

对于Merge Sort的时间复杂度也可以使用这一方法，W(n)=2W(n/2)+n-1，结果大家可以自己算下。

相消法举例：

1.对于Quick Sort排序方法，先确定首元素x，它可能的位置有n种，划分为2个子问题，一种可能输入的时间为T(0)+T(n-1)+n-1，类似的总的时间为2[T(1)+T(2)+...+T(n-1)]+n(n-1）。

T(n)=2/n T(i)+O(n), n>=2, i为1至n-1的遍历，这里需要增加一个nT(n)，然后令两方程相减，以消除其他T(i)项。只保留T(n)和T(n-1)的关系。

最后计算的T(n)=Θ(nlogn)。

主定理举例：

1.主定理的介绍文章，相当于一个套路，有这种递归方程的都可以尝试进行迅速求解。

其中n-1为合并排序的次数，

PS.由于笔记里的一些公式和图表不好画在简书里，大家可以看看文章链接，便于理解。

明天会把这些理论知识的习题做一做，并继续保持每天刷Java题目的数量，至少5题/天。

谢谢大家！