算法复杂度分析

Lecture1 算法复杂度分析

Polynomial-Time 多项式时间

Worst-Case Analysis 最坏情况分析

Average-Case Analysis 平均情况分析

随机的输入

Asymptiotic Order of Growth

将不同算法规模以规范的形式表示

Upper bounds 上界

使用 $O(f(n))$ 表示算法 $T(n)$ 的时间复杂度，存在 $c$ 使得 $T(n)\le cf(n)$

例如 $T(n)=\sum _{i=0}^k{a}_i{n}^i\le \sum _{i=0}^k|a_i|n^i\le \sum _{i=0}^k|a_i|n^k\le c{n}^k$，即 $T(n)$ 具有 $O(n^k)$ 的时间复杂度

Lower bounds

下界

Tight bounds

$\Theta (f(n))$ 表示上下界相同

例

对于 $f(n),g(n)$，有 m a x { f , g } = Θ ( f ( n ) + g ( n ) ) max\{f,g\} = \Theta(f(n) + g(n)) max{f,g}=Θ(f(n)+g(n))

证

m a x { f , g } ≤ f ( n ) + g ( n ) , 2 m a x { f , g } ≥ f ( n ) + g ( n ) max\{f,g\} \leq f(n) + g(n), 2max\{f,g\} \geq f(n) + g(n) max{f,g}≤f(n)+g(n),2max{f,g}≥f(n)+g(n)，故 ( f ( n ) + g ( n ) ) ≥ m a x { f , g } ≥ 1 2 ( f ( n ) + g ( n ) ) (f(n) + g(n)) \geq max\{f,g\} \geq \frac 12 (f(n) + g(n)) (f(n)+g(n))≥max{f,g}≥21​(f(n)+g(n))，分别满足上下确界定义