AlgorithmComplexity

前言：函数的增长

• 算法的渐进效率：我们关心当输入规模无限增加时，算法的运行时间如何随着输入规模的变大而增加。例子：输入规模增大，最坏情况运行时间为的归并排序战胜最坏情况运行时间为的插入排序；

• 我们设最坏情况运行时间函数为；

• 算法分析的种类：
  最坏情况（Worst Case）：任意输入规模的最大运行时间。（Usually）
  平均情况（Average Case）：任意输入规模的期待运行时间。（Sometimes）
  最佳情况（Best Case）：通常最佳情况不会出现。（Bogus）

渐近记号（Asymptotic Notation）

• 渐进记号是应用于函数上的记号。

• 渐进记号刻画算法的运行时间，为了全面性（综合覆盖所有输入），提出了不同的渐进符号。

• 通常有 、 和 记号法。 记号渐进地给出了一个函数的上界和下界，当只有渐近上界时使用 记号，当只有渐近下界时使用 记号。尽管技术上 记号较为准确，但通常仍然使用 记号表示。

• 使用 记号法（Big O Notation）表示最坏运行情况的上界。

• 如下的函数都是渐进非负的，也就是当足够大，非负。

• 渐进记号出现在公式中，出现在等式右边，可以视为某一个不关心的匿名函数，如：
  
  出现在等式左边，表示左边无论是什么匿名函数，右边总有一个匿名函数使得等式成立，例如：
  

前示

image.png

记号

• 定义： ：存在正常量使得对所有，有

• 表示一个函数集合， ；

• 是的渐进紧确界。

记号

• 定义： ：存在正常量使得对所有，有。

• 只有一个渐进上界时，使用记号。

• 代表,因此是一个比更强的概念，有;

记号

• 定义： ：存在正常量使得对所有，有。

• 只有一个渐进下界时，使用记号。

记号

• 是一个非渐进紧确的上界。

• 定义： ：存在正常量 ，存在常量，使得对所有，有。

• 也就是说当趋于无穷时， 比大至少一个数量级。

• 引入的原因：提供的渐进上界可能是也可能不是渐进紧确的。例子：
  不是渐进紧确的。

记号

• 是一个非渐进紧确的下界。

• 定义： ：存在正常量 ，存在常量，使得对所有，有。

• 也就是说当趋于无穷时， 比大至少一个数量级。

[图片上传中...(image.png-114a48-1565404116808-0)]

comlexity table