\(8.2\) 渐进分析介绍

1.简化的分析流程

We can do the following steps to simplify our analysis: * Only consider the worst case. * Pick a representative operation (aka: cost model) * Ignore lower order terms * Ignore multiplicative constants.

2.\(Big-Theta\)

  当对于任一比\(N_0\)大的\(N\)，存在\(k_1\)、\(k_2\)使得\(k_1·f(N)\leq R(N)\leq k_2·f(N)\)，那么：\(R(N)\in \Theta(f(N))\)。

  我们可以用\(\Theta\)来衡量程序的增长阶数，通过确定增长函数的上界和下界，我们相当于“确定”了增长函数。

3.\(Big-O\)

  \(O\)可以看作是增长函数的“不等关系”，即“大于等于”。例如，我们可以说\(R(N)\in O(f(n^2))\)。

  一般地，如果对于任一比\(N_0\)大的\(N\)，存在\(k_1\)使得\(R(N)\leq k_1·f(N)\)，有：\(R(n)\in O(f(n))\)。