时间复杂度&Big-O

时间复杂度&Big-O

• $O(f(n))$: 上界
  • $\exists c>0,\forall n>>2,T(n)\le f(n)$
• $\Omega (f(n))$: 下界
  • $\exists c>0,\forall n>>2,T(n)\ge f(n)$
• $\Theta (f(n))$: 确界
  • $\exists c_1,c_2>0,\forall n>>2,c_1\cdot f(n)\ge T(n)\ge c_2\cdot f(n)$

辨析

$O(1)$

一定不含循环？不一定

for (int i = 0; i < n; i += n/2025 + 1); // 常数

一定不含分支？不一定

if (false) goto UNREACHABLE;

一定不含递归？不一定

if (false) neverCalled();

$O({\log }^{c}n)$

常底数和常数次幂的取值均不影响。

$O(2^n)$

SubsetSum 问题：$O(2^n)$ 复杂度的算法已经是最优。

级数

• 算数级数：与末阶平方同阶

$$\sum _{k=1}^{n}k=1+2+\cdots +n=O(n^2)$$

• 幂方级数：比幂次高一阶

$$\sum _{k=1}^n{k}^2=O(n^3)$$ $$\sum _{k=1}^n{k}^d\approx {\int }_0^n{x}^{d}dx=O(n^{d+1})$$

• 几何级数：与末阶同阶

$$\sum _{k=0}^n{a}^k=O(a^n)$$

• 收敛级数：$O(1)$

$$\sum _{k=2}^n\frac{1}{(k-1)k}=1-\frac{1}{n}=O(1)$$ $$\sum _{\text{k is a perfect power}}\frac{1}{k-1}=\frac{1}{3}+\frac{1}{7}+\cdots =1=O(1)$$ $$\sum _{i=1}^{\infty }(1-\lambda )\cdot k{\lambda }^{k-1}=\frac{1}{1-\lambda }=O(1)$$

• 调和级数：

$$\sum _{k=1}^n\frac{1}{k}=\ln n+\gamma +O\left(\frac{1}{2n}\right)=\Theta (\log n)$$

• 对数级数：

$$\sum _{k=1}^n\ln k=\ln \prod _{k=1}^{n}k=\ln n!=\Theta (n\log n)$$

• 其他：

$$\sum _{i=0}^n{\log }_{2}i=O(n\log n)$$ $$\sum _{k=1}^{n}k\cdot \log k=O(n^2\log n)$$ $$\sum _{k=1}^{n}k\cdot 2^k=O(n\cdot 2^n)$$