算法（2）

算法时间复杂度

算法时间复杂度的定义

在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随 $n$ 变化情况并确定 $T(n)$ 的数量级。算法的时间复杂度，也就是算法的时间量度记作： $T(n)=O(f(n))$ 它表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中 $f(n)$ 是问题规模 $n$ 的某个函数

推导大O阶

• 用常数 $1$ 取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是 $1$，则去除与这个项相乘的常数

最后推导出的结果就是大 $O$ 阶

常数阶

算法的时间复杂度为 $O(1)$

注

不论这个常数是多少，都记作 $O(1)$，而不能是$O(3)、O(12)$

对于分支结构而言，不论是真还是假，执行次数为恒定的，不会随着n的变大而变化，所以单纯的分支结构（不包含在循环结构中），其时间复杂度也是 $O(1)$

线性阶

代码要执行 $n$ 次，时间复杂度就为 $O(n)$ ——执行 $n$ 次复杂度为 $O(1)$ 的算法

• 我们要分析算法的复杂度，关键就是要分析循环结构的运行情况

对数阶

时间复杂度为 $O(logn)$

平方阶

循环嵌套，复杂度为 $O(n)$ 的算法再循环 $n$ 次

• 算法时间复杂度为 $O(n^2)$
• 如果为嵌套循环$m$ 次 则为 $O(n*m)$

常见的时间复杂度

执行次数函数	阶	非正式术语
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2 + 2n +1$	$O(n^2)$	平方阶
$5log_2 n + 20$	$O(logn)$	对数阶
$2n + 3nlog_2 n + 19$	$O(nlogn)$	$nlogn$ 阶
$6n^3 + 2n^2 + 19$	$O(n^3)$	立方阶
$2^n$	O(2^n)	指数阶

💡

$O(1)<O(log n)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

最坏情况与平均情况

• 最坏情况运行时间是一种保证，那就是运行时间将不会再坏了

💡

在应用中，这是一种最重要的要求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间

• 平均运行时间是所有情况中最有意义的，因为它是期望的运行时间
• 一般在没有特殊说明的情况下，都是指最坏时间复杂度

算法空间复杂度

• 算法空间复杂度通过计算算法所需的储存空间实现

算法空间复杂度的计算公式记作：$S(n)=O(f(n))$ ，其中， $n$ 为问题的规模，$f(n)$为语句关于n所占储存空间的函数

💡

通常我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不限定词地使用“复杂度”时，通常指时间复杂度