相比于 CS61B，这门课知道的人就少一些了。
据说是刷 leetcode 的神课，学习中，记录一下过程。

L1

乘法运算时间复杂度
Card Suez alogrithm
分治：
A=Xh*Yh,B=Xl*Hl,D=(Xh+Xl)*(Yh+Yl)
O(nlg3)
Python 中超过 70 位的乘法运算才会用该算法。

L2

Fibonacci 数列
fast matrix powering
[[1,1],[1,0]]*[f1,f0]=[f1+f0,f1]=[f2,f1]
A^n*v
A=QA*Qt(A 是对称矩阵)
QtQ=I

Alg Flops Runtime
recuse exp(n) exp(n)
iter n n²
matrix powering logn <=n^2lgn 近似于 n²

算法符号：
f,g 是两个表示正数的函数。
(“Big Oh”) f=O(g) 存在 C>0,对于任意 n,f(n)<=c.g(n)
(“little Oh”) f=o(g) lim n->无限， f(n)/g(n) =0
("Big Omega") f=Omega(g) if g=O(f),Omega 通常表示下限
("little Omega") f=w(g) if g=o(f)
("Theta") f=Theta(g) if f=O(g) 且 f=Omega(g)

T(n) 分治法通用计算公式：

T(n)<=a*T(n/b)+c*n^d
结论

L3

矩阵乘法

通常的矩阵分治法：
T(n)<=8*T(n/2)+c*n²
T(n)=O(n³ )
这和普通的 LOOP 循环运算量一致。

Strassen '69 的算法
T(n)=7*T(n/2)+c*n²
T(n)=O(n^log27 )=O(n^2.807 )
在实际的矩阵运算中会经常用到 Strassen 的算法。

排序

通常的排序算法都是 O(nlogn) 的时间复杂度
Han ‘02 sorting in O(nloglogn)(Deterninstic)
Han-Tropup '02 O(n*sqrt(loglogn) (Random)
对于比较的排序算法，可以知道 n 个节点有 n! 的排序方式。
假设这些节点都在 2 叉树的页节点上。
可以证明：树的深度 =Theta(Nlogn)
基于比较的所有算法时间复杂度不会超过 Nlogn

查找

查找数列中的 TopN
QuickSelect
类似快排，需要选择合适的 Pivot

T(n)<=O(n)+n/5O(1)+T(n/5)+O(n)+T(7n/10)<=T(9/10n)+c*n
所以这个 QucikSort 是 O(n) 的。

L4

多项式乘法

Loop 循环：
T(n)=O(n² )

FFT
FFT 的核心思想如下：通过分治，降低运算次数。
T(N)=2*T(N/2)+O(N)
T(N) = O(Nlogn)

实现方式：

Cross correlation(互相关函数)

问题定义：

FFT 方法：