MIT 6.006 Algorithms Lecture1

课程主要讨论的： 8 modules

Algorithmic Thinking : Peak Finder
Sorting & Trees : Event Simulation
Hashing : Genome Compasions
Numeric : RSA Encryption
Graphs: Rubicks Cube
Shortest Path: example Cal Tech -> MIT
Dynamic Programing: Image compression
Advanced Topic:

Peak Finder

从一维的上来讲：
比如说有一个一位数组，如下：
a b c d e f g h i
1 2 3 4 5 6 7 8 9
其中a~i都是数字
Peak的定义：如果位置2是一个Peak，那么要满足b>= a并且b>=c
最左边和最右边只需要看一另外一边是否满足即可。
现在问题是：如果存在Peak的话找到一个Peak

最直接的算法：
从左向右开始遍历判断，知道找到或者结束，这样的时间复杂度最差是O(n)

Divde & Conquer Algorithom
也就是二分法
时间复杂度上面的计算：T(n) = T(n/2) + O(1)
为什么要机上O(1)呢，因为还要多算一次另外一边的比较。
我们还可以得到T(1)=O(1)
那么在最终我们可以它的时间复杂度是O(log2n)

那么在二维上面是怎样的呢？

那么对应的数值要大于它的上下左右才可以称之为是一个Peak

这里我们需要用一种算法称为：Greedy Ascent Algorithm（）

如果同样的暴力遍历的话，需要的时间复杂度为O(mn)

同样在二维中我们同样可以运用二分的方法：

复习课：

N！ 约等于根号2πN乘以N/e的N方

算法复杂度中的LOG是以底数为2的