跳转至

时间复杂度分析

符号说明

\(O\) 记号

定义：若存在正常数 \(c\)、\(n_0\)，使得对所有 \(n\ge n_0\)，有 \(0\le f(n)\le cg(n)\)，则记 \(f(n)=O\big(g(n)\big)\)。

\(O\big(f(n)\big)\)：时间复杂度上界0为 \(f(n)\)；

大O时间复杂度

\(\Omega\) 记号

定义：若存在正常数 \(c\)、\(n_0\)，使得对所有 \(n\ge n_0\)，有 \(0\le cg(n)\le f(n)\)，则称 \(f(n)=\Omega\big(g(n)\big)\)。

\(\Omega\big(f(n)\big)\)：时间复杂度下界为 \(f(n)\)；

大Omega时间复杂度

\(\Theta\) 记号

定义：若存在正常数 \(c_1\)、\(c_2\)、\(n_0\)，使得对所有 \(n\ge n_0\)，有 \(0\le c_1g(n)\le f(n)\le c_2g(n)\)，则称 \(f(n)=\Theta\big(g(n)\big)\)。

\(\Theta\big(f(n)\big)\)：时间复杂度确界

大Theta时间复杂度

主定理

主定理可以求解部分递归式，因此可以求解一些递归函数的时间复杂度。对于递归式：

\[ T(n)=aT(\frac{n}{b})+f(n) \]

按 \(n^{log_ba}\) 和 \(f(n)\) 的大小关系分三种情况：

  • 若 \(f(n)=O(n^{log_ba-\epsilon})\)，其中常数 \(\epsilon>0\)，则 \(T(n)=\Theta(n^{\log_ba})\)；
  • 若 \(f(n)=\Theta(n^{\log_ba}\log^kn)\)，其中指数 \(k\ge 0\)，则 \(T(n)=\Theta(n^{\log_ba}\log^{k+1}n)=\Theta\big(f(n)\log n\big)\)；
  • 若 \(f(n)=\Omega(n^{\log_ba+\epsilon})\)，其中常数 \(\epsilon>0\)，且 \(f(n)\) 满足“Regularity condition”，则 \(T(n)=\Theta\big(f(n)\big)\)；

Regularity condition：存在常数 \(c<1\) 和 \(n_0\)，使得对于任意 \(n>n_0\)，\(af(\frac{n}{b})<cf(n)\)

注意，主定理不能涵盖所有情况。例如：

\[ T(n)=2T(\frac{n}{2})+O(n\log^k n) \]

就不能使用主定理解决，因为它不满足 “Regularity condition”。即使我们知道 \(f(n)=O(n^{\log_ba}log^k{n})\) 时递归式的解为 \(T(n)=O(n^{\log_ba}log^{k+1}{n})\)。

技巧

主定理告诉我们，如果能把一个问题分解成规模较小的若干子问题，即使合并的时间复杂度为 \(O(n)\)，也可以将时间复杂度降低为 \(O(n\log n)\)。例如：

  • 归并排序；
  • 快速排序；
  • cdq 分治；
  • FFT；
  • 点分治；

调和级数

当 \(n\) 为正整数，有

\[ \ln(n+1)\le \sum_{i=1}^{n}{\frac{1}{i}}\le \ln(n)+1 \]
证明
\[ \begin{align*} \sum_{i=1}^{n}{\frac{1}{i}}\ &=\int_1^{n+1}\frac{dx}{\lfloor x\rfloor}\\ &\ge\int_1^{n+1}\frac{dx}{x}\\ &=\ln x \ \Big|_1^{n+1}\\ &=\ln(n+1) \end{align*} \]
\[ \begin{align*} \sum_{i=1}^{n}{\frac{1}{i}}\ &= 1+\sum_{i=2}^{n}{\frac{1}{i}}\\ &=1+\int_1^{n}\frac{dx}{\lceil x\rceil}\\ &\le 1+\int_1^{n}\frac{dx}{x}\\ &=1+\ln x \ \Big|_1^{n}\\ &=1+\ln(n) \end{align*} \]

推论

\[ \sum_{i=1}^{n}{\frac{1}{i}}=\Theta(\log n) \]
\[ \lim_{n\rightarrow +\infty}(\frac{\sum_{i=1}^{n}{\frac{1}{i}}}{\ln(n)})=1 \]

参考文献