Asymptotics

CS61b算法部分的第一个lecture（中英混记）。记录的是lec的主要脉络。

General Goal

这部分引出核心问题——“如何衡量算法效率”。

Efficiency comes in two ways
- 编程成本（programming cost）<– 61b前半程的关注点
- 执行成本（execution cost）<– 现在开始的关注点
  - time cost
  - memory cost
引出问题：How to measure code efficiency？
因此这一讲的目标是引入衡量算法效率的正式标准

这部分由浅入深展示了几个可以衡量程序效率的方法。

scrnshot

这部分首先介绍算法效率多大程度上受到增长规模（order of growth）的影响，然后引出能够简化渐进分析的方法。

Order of Growth的影响
- 基本原则是，在分析效率时，只关注asymptotic behavior（即N趋向无穷大时的表现）
- 基于这个原则，可以观察比较N无穷大时的函数形状
- 暂时称这个函数形状为order of growth，比如它可以是line、cubic、quadratic etc.
- 也就是说，我们可以通过Order of Growth来衡量算法效率
但目前的分析增长规模的方式（symbolic count）不够简单，在数学上也不太严谨，所以需要将其简化：
1. 只看worst cast count
2. 只选一个有代表性的操作来count
3. 只看对order影响最大的一项，比如：n^3~~+n^2+1~~
4. 忽略系数
simplification/1
到这步为止，分析时需要1）计算一整个表格，2）挑出一个代表性count，3）简化。这种分析步骤还可以进一步简化：
- 一种是直接看着代码，选择某个运算符进行计数
Approach1-based on exact count
- 更加简单的一种是几何上的分析（假设边是$N-1$，直接得出$N^2$）
Approach2-simpler geometric argument

最后介绍渐进分析的常用记号Big Theta（即Order of Growth）和Big O。

可以用Big Theta来描述某一程序运行时间的增长速率。

假设有一个runtime function $R(n)$，如果$R(n)$的order of growth（函数形状）是$f(N)$

则记作： $$ R(n) \in \Theta (f(N)) $$

$$ R(n) \in \Theta (f(N)) $$

的意思是存在正常数$k_1$, $k_2$，使得 $$ k_1 · f(n) \leq R(N) \leq k_2 · f(N) $$ 对$N>N_0$（i.e. very large N）的所有数均成立。

Big Theta demo

Big Theta更像是描述一种“等于”的关系（某一函数的增长速度等于xx），而Big O描述的是“小于等于”的关系。

$$ R(n) \in \Theta (f(N)) $$

的意思是存在正常数$k_2$，使得 $$ R(N) \leq k_2 · f(N) $$ 对$N>N_0$（i.e. very large N）的所有数均成立。

$$ N^3+3N^4 \in \Theta(N^4) $$

$$ N^3+3N^4 \in O(N^6) $$

	Informal meaning	Family	Family Members
Big Theta$$\Theta(f(N))$$	Order of Growth is f(N)	$\Theta(f(N^2))$	$$N^2/2$$$$2N^2$$$$N^2+38N$$
Big O $$O(f(N))$$	Order of growth is less than or equal to f(N)	$O(f(N^2))$	$$N^2/2$$$$2N^2$$$$lg(N)$$