时间复杂度和空间复杂度


时间复杂度

针对不同规模的输入,算法的执行时间各是多少?如果将某一算法为了处理规模为n 的问题所需的时间记作 T(n),那么随着问题规模 n 的增长,运行时间 T(n)将如何增长?我们将 T(n)称作算法的时间复杂度。


如果存在正常数 a、N 和一个函数 f(n),使得对于任何 n > N,都有
T(n) < a × f(n)
我们就可以认为在 n 足够大之后,f(n)给出了 T(n)的一个上界。对于这种情况,我们记之为
T(n) = O(f(n))
这里的 O 称作“大 O 记号(Big-O notation)”

以冒泡排序为例:
该算法由内、外两层循环组成。内循环从前向后依次检查各相邻的元素对,如有必要,则交换逆序的元素对,因此在每一轮内循环中,至多需要扫描和比较n-1 对元素,至多需要交换n-1 对元素。无论是比较元素大小还是交换元素的位置,都属于基本操作,故每一轮内循环至多需要执行 2(n-1)次基本操作。另外,根据 引理一.1,外循环至多执行n-1 轮。因此,总共需要执行的基本操作不超过 2(n-1)^2次。若取a=2 和f(n)=n^2
,则有
T(n) < 2 × n^2
也就是说
T(n) = O(n^2)
以上可以看出,大 O 记号实质上是对算法执行效率的一种保守估计⎯⎯对于规模为 n 的任意输
入,算法的运行时间都不会超过 O(f(n))。

Last modification:March 31st, 2020 at 12:58 pm
如果觉得我的文章对你有用,请随意赞赏