算法系列——3、函数的增长(i.渐进记号)

type

算法学习系列。3、函数的增长之渐进记号

前两节中,我们简单地刻画了算法效率。而在这里,我们将研究算法的渐进效率,即研究当输入规模无限增大时,算法的运行时间如何随输入规模的变大而增加。

在这里,我们将了解几种标准方法来简化算法的渐进分析。本文将首先定义几类渐进记号

刻画插入排序最坏情况运行时间时,我们用到了$\Theta(n^2)$,正如文中所说的,我们忽略了原本函数的某些细节,它描述的是最坏情况。而在这里,我们将看到完全适用于刻画任何输入的运行时间的渐进记号(综合性的,覆盖所有输入,而非仅仅最坏情况)

我们先给出三个图像:

a

b

c

下面我们将结合这三种图像对三种渐进记号进行探讨。

$\Theta$记号

待续

助力本站发展