算法导论

目标一：解决计算问题，除此之外还有更多。more than that
目标二：证明正确性
目标三：证明更高效
目标四：可以和其他人讲明白为什么正确且高效

算法基础

算法就是用来求解问题的，我们想求解一组通用的问题，而不是固定的问题。算法的实现就是一个函数，给定一组输入，得到一个正确的输出。

数学归纳法证明算法的正确性。

循环不变式主要用来帮助我们理解算法的正确性。我们必须证明三条性质

初始化：循环的第一次迭代之前它为真
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的

通过循环不变式证明插入排序是正确的，下面是插入排序的伪代码：

insert_sort(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i+1] = A[i]
            i--
        A[i+1] = key

循环不变式开始的时候，j = 2的时候，A[1]…A[j-1]里面只有一个元素A[1]，当然是已排序的。循环不变式成立
保持：证明每次迭代保持循环不变式，非形式化的来看，4-7行将A[j-1],A[j-2]等向右移动，第8行将key插入合适的位置，子数组由原来的A[1]…A[j-1]组成，且已经排好序，下一次迭代增加j将保持循环不变式。

如果是形式化的处理，还需要证明while循环的循环不变式。我们不愿陷入形式主义的困境，所以只根据非形式化的来看。
终止：for 循环的终止条件是 j > A.length, 因为每次循环j+1，所以必然会有j = A.length + 1,我们的子数组A[1]…A[j-1]，就变成了A[1]…A[A.length]由原来的A[1]…A[A.length]组成，且已排好序。因此算法正确

练习1.重新insert_sort，使排序变成降序

insert_sort(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] < key
            A[i+1] = A[i]
            i--
        A[i+1] = key

数据结构和动态数组

Interface(API/ADT): 你想做什么？是一种规范，定义了支持哪些操作。可以理解为问题。
Data Structure: 实际怎么做，数据实际的表示形式。算法对于操作的支持。可以理解为解决方案。

接口：

Sequence
- Static Sequence Interface: 静态的，数量不可变的。
  - build(x): 新建一个Static Sequence。
  - len(): 返回数量
  - iter_seq(): 迭代器
  - get_at(i): 获取i下标的元素
  - set_at(i, x): 设置i下标的元素为x
  - get_first()
  - get_last()
  - set_first()
  - set_last()
- Dynamic Sequence Interface: 动态的，数量可变的
  - 支持上面所有
  - insert_at(i, x): 插入某一个位置
  - delete_at(i): 删除某一个位置的元素
  - insert_first()
  - insert_last()
  - delete_fist()
  - delete_last()

数据结构：

Linked List

Set And Sorting

接口

Set
- Container
  - build(A): 根据一个iterable的A,创建
  - len(): 返回数量
- Static
  - find(k): 返回一个set中的元素
- Dynamic
  - insert(k): 插入一个元素到set
  - delete(k): 从set中删除一个元素
- Order
  - iter_ord(): 迭代器
  - find_min(): 获取最小的key
  - find_max(): 获取最大的key
  - find_next(k): 获取比k大的下一个key
  - find_pre(k): 获取比k小的上一个key

数据结构

Array
Sorted Array

排序

破坏性：用一个新的排序后的数组B覆盖数组A
原地排序：仅仅用O(1)空间来排序

permutation Sort