渐进符号

习题预习

1. 什么是大O符号？它有什么用途？

2. 何谓Ω符号和Θ符号？它们与大O符号有何不同？

3. 给出以下函数的大O符号：f(n)=2n^2+3n+1。

4. 给出以下函数的Ω符号：f(n)=log(n)+5。

5. 如果算法A的时间复杂度为O(n)，而算法B的时间复杂度为O(n^2)，那么在什么情况下A的效率高于B？

说明知识

Asymptotic Notations 是一个衡量算法运行时间复杂度的工具，其关注算法运行时间随着输入大小增长的趋势。以下是三种通常使用的 Asymptotic Notations：

1. 大O符号（Big O Notation）
   Big O Notation 用于描述算法最坏情况下的时间复杂度。当输入数据增长时，算法的时间复杂度与某个常数 k 成正比，而且当输入数据数值增大时，此常数 k变得越来越不重要。
   比如说：当n趋向无限大时，O(n) 就是一种线性时间复杂度算法。简单来说，因为一个有n个元素的列表，最多需要检查n次才能找到目标元素，所以时间复杂度是O(n)。

2. 大Ω符号（Omega Notation）
   Ω Notation 用于描述算法最优情况下的时间复杂度。当输入数据增长时，算法的时间复杂度与某个常数 k 成正比，且算法常数 k 的值是趋近最小的。
   比如说：当n趋向无限大时，Ω(n lg n) 是快速排序的运行时间复杂度。简单来说，当列表经过排序后数据的查找时间变得更加快速，此类算法优于平均水平，所以时间复杂度是Ω(n lg n)。

3. 大θ符号（Theta Notation）
   θ Notation 用于描述算法的平均情况下的时间复杂度。当输入数据增长时，算法的时间复杂度和某个常数 k 成正比，且算法常数 k 的趋近平均值。因为平均时间复杂度并不总是最坏情况复杂度或最优情况复杂度的平均值，因此θ Notation 是一个更为精确的算法分析工具。
   比如说：当n趋向无限大时，θ(n) 是一个简单查找算法的时间复杂度。简单查找需要检查列表中的每个元素，所以时间复杂度是 θ(n) 。例如输入一个列表并且查找元素。

总之，Asymptotic Notations 是一种帮助计算设计和改进算法的工具，尤其对那些必须处理大量复杂而大量的数据的算法来说，更是必要的。

条列重点

1. 渐进符号代表算法的运行时间在大规模输入情况下的增长速度。
2. 渐进符号分为大O符号、Ω符号和Θ符号。
3. 大O符号表示算法的最坏运行时间，即在所有输入情况下，算法的运行时间都不会超过O(某个函数)。
4. Ω符号表示算法的最好运行时间，即在某些输入情况下，算法的运行时间不会低于Ω(某个函数)。
5. Θ符号代表算法的平均运行时间或者所有输入情况下的紧密边界，即算法的运行时间在Θ(某个函数)。
6. 渐近符号不表示精确的运行时间，但它们提供了有关算法运行时间增长速度的重要信息。
7. 渐进符号通常用于分析算法的复杂度，并比较不同算法之间的性能。

知识测验

1. 给定一个算法的时间复杂度为O(n log n)，请问当n趋近于无限大时，此算法的执行时间会如何变化？

答案：当n趋近于无限大时，此算法的执行时间会随着n log n的增加而增加。

2. 给定一个算法的时间复杂度为O(n^2)，请问当n趋近于无限大时，此算法的执行时间会如何变化？

答案：当n趋近于无限大时，此算法的执行时间会随着n^2的增加而急剧增加。

3. 给定一个算法的时间复杂度为O(2^n)，请问当n趋近于无限大时，此算法的执行时间会如何变化？

答案：当n趋近于无限大时，此算法的执行时间会急剧增加，甚至可能导致程序崩溃。

4. 给定一个算法的时间复杂度为O(n log n)，请问此算法的最坏情况时间复杂度是多少？

答案：此算法的最坏情况时间复杂度是O(n log n)。

5. 给定一个算法的时间复杂度为O(1)，请问此算法的执行时间是否随着n的增加而增加？

答案：此算法的执行时间不会随着n的增加而增加，而是恒定的。