CH3：Growth of Functions

MindMap

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9nlpmj1u-1659616062952)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220605154233378.png)]

Asymptotic Growth

分析算法时我们对算法输入规模为n时的最坏情况下运行时间函数感兴趣

• 不考虑常数项
• 不考虑低阶项

3.1 Asymptotic Notation

3.1.1 O-Notation

（1）定义

O ( g ( n ) ) = { f ( n ) : There exists positive c and  n 0  such that  0 ≤ f ( n ) ≤ c g ( n )  for all  n ≥ n 0 } O(g(n)) = \{f(n):\text{There exists positive c and }n_0\text{ such that } 0\leq f(n)\leq cg(n)\text{ for all }n\geq n_0\} O(g(n))={f(n):There exists positive c and n0​ such that 0≤f(n)≤cg(n) for all n≥n0​}

• 正整数c
• 正整数n0
• g(n)是最高次项
• exists：存在即可

$O(g(n))$是一个满足上述条件的运行时间函数的集合

---

$O(.)$：用于渐进上界函数 $\text{is used to asymptotic upper bound a function}$

$O(.)$：用来表示最坏情况的运行时间$\text{is used to bound worst-case running time}$

---

（2）Example

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3O8FRcV8-1659616062959)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220605145849484.png)]

（3）使用情况

当我们说道“运行时间是O(n)”时，我们指的是最坏情况下的运行时间是O(n)

通常写为：$f(n)=O(g(n))$，而不是$f(n)\in O(g(n))$——虽然是个集合

我们也在等式中使用$O(n)$，例子：
$$2n^2+3n+1=2n^2+O(n)$$
$O(1)$表示常数时间

3.1.2 $\Omega -Notation$

（1）定义

Ω ( g ( n ) ) = { f ( n ) : There exists positive c and  n 0  such that  0 ≤ c g ( n ) ≤ f ( n )  for all  n ≥ n 0 } \Omega(g(n)) = \{f(n):\text{There exists positive c and }n_0\text{ such that } 0\leq cg(n)\leq f(n) \text{ for all }n\geq n_0\} Ω(g(n))={f(n):There exists positive c and n0​ such that 0≤cg(n)≤f(n) for all n≥n0​}

我们使用$\Omega (.)$来表示运行时间的下界

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kPWbvcUb-1659616062960)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220605150431979.png)]

（2）Example

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x6K4u159-1659616062960)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220605150735127.png)]

when we say “the running time is $\Omega (n^2)$” we mean that the best-case running time is $\Omega (n^2)$ ——the worst case might be worse.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cDwMA58J-1659616062961)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220605150910298.png)]

3.1.3 $\Theta -Notation$

（1）定义

Θ ( g ( n ) ) = { f ( n ) : There exists positive  c 1 ， c 2  and  n 0  such that  0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n )  for all  n ≥ n 0 } \Theta(g(n)) = \{f(n):\text{There exists positive }c_1，c_2\text{ and }n_0\text{ such that } 0\leq c_1g(n)\leq f(n)\leq c_2g(n) \text{ for all }n\geq n_0\} Θ(g(n))={f(n):There exists positive c1​，c2​ and n0​ such that 0≤c1​g(n)≤f(n)≤c2​g(n) for all n≥n0​}

我们使用$\Theta -Notation$来表示紧致界

充要条件：$f(n)=\Theta (g(n))ifandonlyiff(n)=O(g(n))andf(n)=\Omega (g(n))$

（2）Example

3.1.4 总结

（1）表示法

（2）在等式中的使用

使用$O、\Theta 、\Omega$在函数中替换低阶项简化函数表达