1.1 编程的灵魂——数据结构+算法 = 程序
算法（algorithm）就是解决问题的方法或者过程。
数据结构（data structure）是数据的计算机表示和相应的一组操作。
时空开销增长
- 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。
- 只关心在问题规模扩大时时空开销的增长情况。
程序一：
fact = 1;
for (int i = 1;i <= n; i++)
fact *= i;
共执行了n个基本操作；
程序二：
sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
sum += a[i][j];
执行了n^2个基本操作；
程序一的渐进时间复杂度低，因此更优。
复杂度分析的常用符号
- 若存在两个正常数c和n0，对任意的 n > n0 都有 |T(n)|<=c|f(n)|，则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。
- T(n)的增长速度不会比f(n)差。
- 大O表示法（big-Oh notation）表示的是运行时间的上限。
- 小o表示法,表示这个上限是“松”的。
简化法则
- 简化的方法是忽略常数和低次项，如 3n^4 + 8n^2 + n + 2 = O(n^4)
复杂度的等级
- 多项式算法
- 它的运行时间随着规模的扩大增长不大，因此叫做有效算法；
- 指数级算法
- 运行时间增长很快，不是有效算法。
- 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性
- 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构
- n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法（如二级检索），分阶段算法（如二分图匹配的 Hopcroft 算法），或者待定参数的算法。a是最后解出的最优参数。
时空辩证关系
- 时间换空间
- 常用方法是重复计算
- 空间换时间
- 常用方法是预处理
P类问题和NP问题
- 如果一个问题可以在多项式时间内被确定机解决，则它属于 P 类问题
- 如果它可以在多项式时间内被非确定机解决，则它属于 NP 类问题
NP完全（NPC）问题
- 满足：
- 属于NP
- NP 中的每个问题都可以使用多项式归约到它
Monte-Carlo算法、RP类问题
- 如果一个问题存在一个随机算法，使得它有50%以上的概率得到期望的结果，那么这个问题属于RP类，该算法称为 Monte-Carlo
(收起)
