2019-02-12 GA Algo

Divide and conquer

T(n)=aT(\frac{n}{a})+f(n)

Merge sort

T(n)=2T(\frac{n}{2})+n
T(n)=\theta(nlogn)

Binary search

T(n)=T(\frac{n}{2})+1
T(n)=\theta(logn)

Stock price

  1. VP1 on A[1..n/2]
  2. VP2 on A[n/2+1..n]
  3. find smallest in A[1..n/2], bigest in A[n/2+1..n]
    T(n) = 2T(\frac{n}{2})+n=\theta(nlogn)

Exponential

Given a, n, output a**n
Naive: T(n)=T(n-1)+1=n
Smart: T(n)=T(n/2)+1=logn

Fibonacci

Naive: O(n)
Geeky: equation
Theorem:
\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^n
\theta(logn)

Lightbulb technique

Karatsuba multiplication

Toy: addition of n-bit numbers, A=a_1,..a_n, B=b_1..b_n
C=AB, O(n^2)
A = A_0A_1
A=A_0\cdot 2^\frac{n}{2}+A_1
B = B_0B_1
B=B_0\cdot 2^\frac{n}{2}+B_1
C=AB=(A_0\cdot 2^\frac{n}{2}+A_1)(B_0\cdot 2^\frac{n}{2}+B_1)=(A_0B_0)2^n+(A_0B_1+A_1B_0)2^\frac{n}{2}+A_1B_1
T(n)=4T(\frac{n}{2})+O(n)
(A_0+A_1)(B_0+B_1)=A_0B_0+(A_0B_1+A_1B_0)+A_1B_1
T(n)=3T(\frac{n}{2})+O(n)

Strassen multiplication

nxn matrix

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容