对时间复杂度$O$符号的一个误解

Posted on

起因是，在twitter上看到有人说“\(O(n! \cdot n)\) is the same as \(O(n!)\)”。当时我看到这句话没啥异议，嗯对啊挺明显的嘛，然后就看到一条评论指出这是错的。好吧，挺惭愧的，我居然没意识到这个问题，这得记录一下。

首先，复习一下渐近符号的定义：

渐近紧界（Asymptotically tight bound） 对于函数\(f(n)\)，如果它的渐近紧界为\(g(n)\)，则\(f(n) = \Theta(g(n))\)，其中： \[ \Theta(g(n)) = \{t(n) : \text{存在正的常数}c_1、c_2\text{和}n_0\text{，使得对于所有的}n \geq n_0\text{都有}0 \leq c_1 \cdot g(n) \leq t(n) \leq c_2 \cdot g(n)\text{成立}\} \] 渐近上界（Asymptotic upper bound） 对于函数\(f(n)\)，如果它的渐近上界为\(g(n)\)，则\(f(n) = O(g(n))\)，其中： \[ O(g(n)) = \{t(n) : \text{存在一个正的常数}c\text{和}n_0\text{，使得对于所有的}n \geq n_0\text{都有}0 \leq t(n) \leq c \cdot g(n)\text{成立}\} \] 渐近下界（Asymptotic lower bound） 对于函数\(f(n)\)，如果它的渐近下界为\(g(n)\)，则\(f(n) = \Omega(g(n))\)，其中： \[ \Omega(g(n)) = \{t(n) : \text{存在一个正的常数}c\text{和}n_0\text{，使得对于所有的}n \geq n_0\text{都有}0 \leq c \cdot g(n) \leq t(n)\text{成立}\} \] 非紧上界（upper bound that is not asymptotic tight） 对于函数\(f(n)\)，如果它的非紧上界为\(g(n)\)，则\(f(n) = o(g(n))\)，其中： \[ o(g(n)) = \{t(n) : \text{对于任意正的常数}c\text{，都存在正的常数}n_0\text{，使得对于所有的}n \geq n_0\text{都有}0 \leq t(n) < c \cdot g(n)\text{成立}\} \] 非紧下界（lower bound that is not asymptotic tight） 对于函数\(f(n)\)，如果它的非紧下界为\(g(n)\)，则\(f(n) = \omega(g(n))\)，其中： \[ \omega(g(n)) = \{t(n) : \text{对于任意正的常数}c\text{，都存在正的常数}n_0\text{，使得对于所有的}n \geq n_0\text{都有}0 \leq c \cdot g(n) < t(n)\text{成立}\} \] 要记住上面的定义，有一个比较方便的方法：

  • \(f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \land f(n) = \Omega(g(n))\)
  • \(f(n) = O(g(n)) \implies \lim_{n \to \infty} \frac{f(n)}{g(n)}\)是收敛的，且极限非0
  • \(f(n) = \Omega(g(n)) \implies \lim_{n \to \infty} \frac{g(n)}{f(n)}\)是收敛的，且极限非0
  • \(f(n) = o(g(n)) \implies \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\)
  • \(f(n) = \omega(g(n)) \implies \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\)

回到最开始的问题：\(O(n! \cdot n)\)和\((n!)\)是什么关系呢？

可以从严格的渐近符号定义中找到它们的关系，这个不难，一个一个定义比对即可。这里我用上面极限的思想来找它们的关系： \[ \begin{equation}\label{proof1} \lim_{n \to \infty} \frac{n! \cdot n}{n!} = \infty \end{equation} \] \[ \begin{equation}\label{proof2} \lim_{n \to \infty} \frac{n!}{n! \cdot n} = 0 \end{equation} \]

所以，\(n! \cdot n = \omega(n!)\)，即\(n!\)为\(n! \cdot n\)的非紧下界，或\(n! \cdot n\)为\(n!\)的非紧上界！

更吸引我注意的是，原评论中还说到了\(O(n!)\)和\(O((n + 1)!)\)，这个更有迷惑性（至少我当时没看出来）。同样，按上面(\(\ref{proof1}\)-\(\ref{proof2}\))的过程，就可以发现\(n!\)为\((n + 1)!\)的非紧下界。这么说，如果我把某个算法的复杂度从\(O(n!)\)改进到\(O((n - 1)!)\)，也是一个挺厉害的工作了？🤔