coursera Algorithm 课程 divide and conquer 第一周笔记（big O（算法复杂度分析）)

O method（算法复杂度分析基本方法）

做big O 分析的原因：

1. 对于高等级的算法分析要知道其“sweet spot”
2. 能超越架构、语言、编译器等进行分析
3. 在不同算法之间比较十分有用

三条假设(规则):

1. 只针对时间最长（最坏情况做分析）
2. 忽略那些常数项和低等级的项
3. 只针对输入数据的规格（N）较大的情况下

常见的几种：

$O(1),O(logN),O(N),O(NlogN),O(N^2),O(2^N)$O(1),O(logN),O(N),O(NlogN),O(N2),O(2N)
时间复杂度上依次升高

各分析定义：

BIG O 分析的数学定义：
$T(N)=O(f(N))$T(N)=O(f(N))的含义是：
如果存在一个C,N0，使所有$N>=N0$N>=N0的数都满足：
$T(N)<=C*f(N)$T(N)<=C∗f(N)
则我们说$T(N)=O(f(N))$T(N)=O(f(N))

$\Omega$Ω分析的数学定义：
$T(N)=\Omega(f(N))$T(N)=Ω(f(N))的含义是：
如果存在一个C,N0，使所有$N>=N0$N>=N0的数都满足：
$T(N)>=C*f(N)$T(N)>=C∗f(N)
则我们说$T(N)=\Omega(f(N))$T(N)=Ω(f(N))

$\Theta$Θ分析的数学定义
$T(N)=\Theta(f(N))$T(N)=Θ(f(N))的含义是：
如果存在一个$C_1,C_2,N0,$C1​,C2​,N0,使所有$N>=N0$N>=N0的数都满足：
$C_1f(N)=<T(N)<=C_2*f(N)$C1​f(N)=<T(N)<=C2​∗f(N)
则我们说$T(N)=\Theta(f(N))$T(N)=Θ(f(N))

练习例子：

$2^{2n} !=O(2^n)$22n!=O(2n):反证法
$2^{n+10} = O(2^n)$2n+10=O(2n)
$2^n!=O(2^{n-1})$2n!=O(2n−1)
$max(f,g) = \Theta(f+g)$max(f,g)=Θ(f+g)