the computational complexity of angry birds
<aside>
可计算算法，渐进复杂度分析
NP and Computational Intractability
</aside>
<aside>
渐进
$$ O(g(n))=\{f(n)\mid \exist c\in R^+,n_0:0\le f(n)\le cg(n),\forall n\ge n_0 \} $$
渐进上界$O$
$$ \Omega(g(n))=\{f(n)\mid \exist c\in R^+,n_0:f(n)\ge cg(n)\ge 0,\forall n\ge n_0 \} $$
渐进下界$\Omega$
$$ \boxed{\le,\ge} $$
紧渐进
$$ \Theta(g(n))=\{f(n)\mid \exist c_1,c_2,n_0:c_1g(n)\le f(n)\le c_2g(n),\forall n\ge n_0 \} $$
紧渐进记号$\Theta$
$$ \boxed{==} $$
非紧界
$$ o(g(n))=\{f(n)\mid \boxed{ \forall c\in R^+},n_0:0\le f(n)< cg(n),\forall \ge n_0 \} $$
非紧上界$o$，等价于两者为同阶函数$\lim_{x\to \infty}\frac{f}{g}=0$
$$ \omega(g(n))=\{f(n)\mid\boxed{ \forall c\in R^+},n_0:f(n)\ge cg(n)\ge 0,\forall n\ge n_0 \} $$
非紧下界$\omega$，等价于原函数为目标函数的高阶函数$\lim_{x\to\infty}\frac{f}{g}=+\infty$
$$ \boxed{<,>} $$
</aside>
从定义看，渐进到某个函数构成的函数集合对应相应记号，那么取特定函数作为代表即可
$$ c,\log n,\log^2n,n,n\log n,n^2,n^3,2^n $$
$f(x)=O(g(x))$ ↔ $f(x)\in O(g(x))$
传递性
反身性
对称性
互对称性
四则运算
常见结果
$$ \sum_i a_in^i=\Theta(n^I),\\ O(\log_a n)=O(\log_b n),a,b\ge 0\\ \log n=O(n^i),\forall i\ge 0\\ n^d=O(r^n),r>1,d>0 $$