计算机书籍出版社：Pearson McGraw-Hill Elserier MIT 阅读指南： 如果对某一主题已经有所了解，可以跳过一些介绍性的小节，直接阅读更高级的内容 预备知识： 理解递归和简单的数据结构（如数组和链表），能够较为熟练的利用数学归纳法进行证明，初等微积分方面的知识。
第一部分 基础知识
第一章 算法在计算中的应用
1.1 算法
可以把算法看成求解良说明的计算问题的工具：问题陈述说明了期望的输入/输出关系，算法则描述一个特定的计算过程来实现该输入/输出关系
算法解决哪种问题
数据结构 ：是一种存储和组织数据的方式，旨在便于访问和修改。没有一种单一的数据结构对所有用途均有效，所以重要的是知道几种数据结构的优势和局限。
技术
算法设计与分析的技术，以便你能和自行设计算法、证明其正确性和理解其效率
难题
关于效率的一般度量是速度。然而有一些问题，目前还不知道有效的解法-NP完全问题
旅行商问题
并行性
多核cpu的算法
1.2 作为一种技术的算法
效率
求解同样问题的不同算法，效率上具有显著的差别。 插入排序 归并排序
算法与其他技术
第二章 算法基础
2.1 插入排序
对于很少量元素的排序，它是一个有效的算法。
class Solution {
public:
vector<int> insertSort(vector<int>& array) {
int len=array.size()
for(int j=1;i<=len;j++){
int cur=array[j];
int i=j-1;
while(i>=0 & array[i]>cur){
array[i+1]=array[i]
i=i-1
}
array[i+1]=cur;
}
return array;
}
};循环不变式与插入排序的正确性
在for循环每次迭代（循环变量取值j）的开始， A[1,j-i] 的元素已经排好序, 剩余的 A[j+1,n] 对应剩下未排序的元素，这些性质称为循环不变式。
- 初始化： 循环的每一次迭代开始，它为真
- 保持：若循环的某次迭代之前为真，那么下次迭代之前仍为真
- 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。
伪代码中的一些约定
2.2 分析算法
RAM(random-access machine)随机访问机模型: 包含真实计算机中的常见指令, 算术指令(加减乘除取余取整幂), 数据移动指令(移动复制赋值), 控制指令(条件循环函数调用)
需要的数学工具包括组合学 概率论 代数技巧等 以及识别一个公式中最有意义的项的能力(代码可读)
插入排序算法分析
运行时间和输入规模
输入规模的概念依赖于所研究的问题，对于研究的每个问题会指出所使用的输入规模和规模度量。运行时间是指执行的基本操作步数。
最坏情况与平均情况分析
往往集中于只求最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。原因是：
- 一个算法的最坏运行情况给出了任何输入的运行时间的一个上界
- 对于某些算法，最坏情况经常出
- “平均情况”往往与最坏情况大致一样差
某些特定情况下, 我们会对一个算法的平均运行时间感兴趣(概率分析、随机化算法)
增长量级
我们真正感兴趣的是运行时间的增长率或增长量级, 所以我们只考虑复杂度公式中最重要的项
an^2+bn+c => an^2n^3 比 n^2 更慢
2.3 设计算法
插入排序使用了增量方法，在排序子数组 A[1,j-1] 后，将单个元素 A[j] 插入到子数组的适当位置，产生排序好的 A[1,j]
分治法，该算法的最坏情况运行时间比插入排序要少的多，分治算法通常很容易确定其运行时间。
2.3.1 分治法
许多有用的算法在结构上是递归的，为了解决一个问题，算法一次或多次递归地调用其自身以解决紧密相关的子问题。这些算法典型地遵循分治法的思想，将原问题分解为几个规模较小但类似与原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时都有三个步骤：
- 分解原问题为若干子问题
- 解决这些子问题，递归地求解各子问题
- 合并这些子问题一的解成原问题的解
归并排序算法完全遵循分支模式：
- 分解待排序的n个元素成两个n/2哥元素的子序列
- 解决：使用归并排序递归地排序两个子序列
- 合并两个已排序的子序列以产生已排序的答案
归并排序
class Solution{
public:
vector<int> mergeSort(vector<int>& array,int startPos, int endPos){
return array;
}
void merge(vector<int>& array, int startPos,int midPos, int endPos){
int n1 = q-p+1;
}
}:2.3.2 分析分治算法
归并排序算法的分析
第三章 函数的增长
3.1 渐近记号
渐近记号、函数与运行时间
Θ记号
theta
O记号
大欧
Ω记号
大omega
定理3.1
等式和不等式中的渐进记号
o记号
小欧
ω记号
小omega
比较各种函数
传递性
自反性
对称性
转置对称性
三分性
3.2 标准记号和常用函数
单调性
向下取整与向上取整
模运算
指数
对数
阶乘
多重函数
多重对数函数
斐波那契数
第四章 分治策略
4.1 最大子数组问题
暴力求解法
O(n^2)
问题变换
使用分治策略的求解方法
分治算法的分析
4.2 矩阵乘法的Strassen算法
一个简单的分治算法
Strassen方法
4.3 用代入法求解递归式
做出好的猜测
微妙的细节
避免陷阱
改变变量
4.4 用递归树方法求解递归式
4.5 用主方法求解递归式
4.6 证明主定理
第二部分 排序和顺序统计量
第六章 堆排序
heapsort, 堆排序的时间复杂度是O(nlgn) 具有空间原址性，空间复杂度O(n)
6.1 堆
p85
int parent(int i){
return i/2 // i>>1
}
int left(int i){
return 2*i // 也可位运算实现 i<<1
}
int right(int i){
return 2*i+1 // i<<1+1
}最大堆（大顶堆）通常用于堆排序算法中、最小堆（小顶堆）通常用于构造优先队列
- MAX-HEAPIFY： 时间复杂度是
O(lgn)，它是维护最大堆性质的关键 - BUILD-MAX-HEAP： 从无序的输入数据中构造一个最大堆的过程， 时间复杂度为
O(n)，线性时间复杂度 - HEAPSORT： 对一个数组进行原址排序，时间复杂度
O(nlgn) - MAX-HEAP-INSERT、HEAP-EXTRACT-MAX、HEAP-INCREASE-KEY和HEAP-MAXIMUM： 利用堆实现一个优先队列，时间复杂度为
O(lgn)
第十五章 动态规划
动态规划与分治方法都是通过组合子问题的解来求解原问题。 动态规划与分治的区别在于：动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子问题（子问题的求解是递归的进行的，将其划分为更小的子子问题）。 在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子问题。 而动态规划算法对每个子子问题只会求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题都重新计算。
动态规划通常用于解决最优化问题
- 刻画一个最优解的结构特征(动态规划转移方程)
- (递归地)定义最优解的值
- 计算最优解的值
- 利用计算出的信息构造一个最优解
递归方法
- 自顶向下递归
动态规划方法
- 带备忘的自顶向下法：仍按照自然的递归形式编写，但过程会保存每个子问题的解（通常保存在一个数组或者散列表中）单选乣一个子问题的解时，过程首先检查是否已经保存过此解，如果是直接返回，从而节省了计算时间。
- 自底向上法
第三部分 数据结构
第十章 基本数据结构
10.1 栈和队列
栈：后进先出 LIFO 队列：先进先出 FIFO
栈
栈操作的实现：empty push pop
队列
队列操作的实现：enqueue dequeue
10.2 链表
链表中的各数据对象按线性排列。
- 单链表
- 双向链表
链表的搜索
链表的插入
链表的删除
哨兵（虚拟头dummyHead）
我们应当慎用哨兵。假如有许多个很短的链表，它们的哨兵所占用的额外存储空间会造成严重的存储浪费。仅当可以真正简化代码时才使用哨兵。
10.3 指针和对象的实现
当有些语言不支持指针和对象的数据类型时的实现。
对象的多数组表示
对象的单数组表示
10.4 有根树的表示
二叉树
分支无限制的有根树
树的其他表示方法
第十一章 散列表 hash table
散列表 hash table是实现字典操作的一种有效数据结构
11.1 直接寻址表
实现：