ch2 算法分析基础¶

1. 计算可追踪性¶

【暴力算法】对于许多非平凡的问题，存在一种自然的暴力搜索算法，可以检验每一个可能的解。对于大小为 \(n\) 输入，通常需要 \(2^n\) 或更多的计算时间，在实践中是不可接受的。

【理想的缩放特性】当输入规模加倍时，算法的运行时间只增加常数倍。如果一个算法的运行时间满足这种特性，则称这个算法是多项式时间算法。如果一个算法的运行时间是多项式时间，我们称这个算法是有效的。

【上界】如果存在常数 \(c>0\)，\(n_0 \ge 0\)，使得对所有的 \(n\ge n_0\) 均有 \(T(n)\le c\cdot f(n)\)，则 \(T(n) = O(f(n))\)，\(f(n)\) 为 \(T(n)\) 的上界。

【下界】如果存在常数 \(c>0\)，\(n_0 \ge 0\)，使得对所有的 \(n\ge n_0\) 均有 \(T(n)\ge c\cdot f(n)\)，则 \(T(n) = \Omega(f(n))\)，\(f(n)\) 为 \(T(n)\) 的下界。

【紧界】如果 \(T(n) = O(f(n))\)，且 \(T(n) = \Omega(f(n))\)，则 \(T(n) = \Theta (f(n)\)，\(f(n)\) 为 \(T(n)\) 的紧界。