算法分析

空间复杂度

递归空间开销较大，尽可能少用。

时间复杂度

渐近上界

如果存在常量 \(c>0\) 和 \(n_0>0\)，使得对 \(\forall n\ge n_0\)，都有 \(T(n)\le c·f(n)\)，则称 \(f(n)\) 是运行时间 \(T(n)\) 的渐近上界，记作 \(T(n)=O(f(n))\).

渐近下界

如果存在常量 \(c>0\) 和 \(n_0>0\)，使得对 \(\forall n\ge n_0\)，都有 \(T(n)\ge c·g(n)\)，则称 \(g(n)\) 是运行时间 \(T(n)\) 的渐近下界，记作 \(T(n)=\Omega(g(n))\).

渐近紧确界

如果存在常量 \(c_1\gt 0,\ c_2\gt 0\) 和 \(n_0\gt 0\)，使得对 \(\forall n\ge n_0\)，都有 \(c_1·h(n)\le T(n)\le c_2·h(n)\)，则称 \(h(n)\) 是运行时间 \(T(n)\) 的渐近紧确界，记作 \(T(n)=\Theta(h(n))\).

对任意 \(T(n)\) 和 \(f(n)\)，我们有 \(T(n)=\Theta(f(n))\)，当且仅当 \(T(n)=O(f(n))\) 且 \(T(n)=\Omega(f(n))\).

当时间复杂度为 \(O(n^2)\)，考虑是否可以优化到 \(O(n\lg n)\).