什么是算法？

一系列解决问题的清晰指令，能够对一定规范的输入，在有限的时间内获得要求的输出

算法的特点：

1. 指令清晰

指令：计算机中的一行代码

清晰：每一条指令不应该具有二义性，即计算机在接收到这条指令时，它的理解是唯一的

2. 输入规范

算法要有输入，且要确定该算法的输入范围

3. 有限性

算法运行的时间是有限的，只要算法能够终止，它的时间就是有限的

4. 输出

输出是任何一个算法必须的，如果一个算法没有输出，它就没有任何意义

算法描述：同一个算法有不同的表达方式

自然语言描述
伪代码描述

伪代码对照：

算法是问题的程序化解决方案，因此它遵循一定的流程

算法分析？

算法分析就是要分析算法的时间效率和空间效率

时间效率也就是时间复杂度，反映的是算法运行需要的时间长度

空间效率也就是空间复杂度，反映的是算法运行需要的存储空间

算法分析的核心是分析算法的时间效率

输入规模越大的算法，其需要的计算时间就越长，同时也与算法实现的程序设计语言、编译器以及运行算法的硬件设备都有关系

对于输入规模很大的算法，其运行时间通常由算法的操作中那些最耗时的操作来确定

四则运算的算法中，通常乘除运算比加减运算耗时更多

基本操作：用算法中最耗时的操作被执行的次数来度量算法的时间

一个算法的运行时间主要与输入规模和基本操作有关

eg.

算法的时间效率对于不同的输入是不同的

时间渐进表示

时间渐进符号：$O$、$\Omega$、$\Theta$

时间效率的渐进表示：

对于足够大的 $n$，函数 $t(n)$ 的上界由 $g(n)$ 的常数倍来确定，即：$t(n) \leq c g(n)$，$c$ 为常数，记为：$t(n) \in O (g(n))$

$t(n)$：算法基本操作执行次数的时间多项式，eg. $t(n) = 3n^{2} + 4n + 5$

$g(n)$：常见的效率类型，eg. $log_{n}$、$n$、$nlog_{n}$

不管 $n$ 如何变化，算法时间多项式的曲线总是在函数 $g(n)$ 的常数倍之下

说明函数 $g(n)$ 对应的效率类型是该算法的下界，即：在最坏情况下，该算法的时间效率为 $O (g(n))$

$\Omega$

对于足够大的 $n$，函数 $t(n)$ 的下界由 $g(n)$ 的常数倍来确定，即：$t(n) \geq c g(n)$，$c$ 为常数，记为：$t(n) \in \Omega (g(n))$

不管 $n$ 如何变化，算法时间多项式的曲线总是在函数 $g(n)$ 的常数倍之上

说明函数 $g(n)$ 对应的效率类型是该算法的上界，即：在最优情况下，该算法的时间效率为 $\Omega (g(n))$

$\Theta$

对于足够大的 $n$，函数 $t(n)$ 的下界和下界由 $g(n)$ 的常数倍来确定，即：$c_{2} g(n) \leq t(n) \leq c_{1} g(n)$，$c_{2}$、$c_{1}$ 为常数，记为：$t(n) \in \Theta (g(n))$

不管 $n$ 如何变化，算法时间多项式的曲线总是在函数 $g(n)$ 的两个常数倍之间

说明函数 $g(n)$ 对应的效率类型是该算法的上界和下界之间，即：在典型输入下，该算法的时间效率为 $\Theta (g(n))$

eg. 算法 1 的时间多项式：$t_{1}(n) = 2n^{2} + 4n + 20$，算法 2 的时间多项式：$t_{2}(n) = 10nlog_{n} + 5n + 3$，问：哪一个算法的效率更高

$\because t_{1}(n) \in \Omega (n^{2}),\;t_{2}(n) \in \Omega (nlog_{n})$

$\therefore$ 算法 2 效率更高

定理：

如果：$t_{1}(n) \in O(g_{1}(n))$ 且 $t_{2}(n) \in O(g_{2}(n))$，则 $t_{1}(n) + t_{2}(n) \in O(max \left\{ g_{1}(n),\;g_{2}(n) \right\} )$

算法的基本效率类型：

如果算法的时间效率属于 $n^3$ 以上时，在输入规模 $n$ 逐渐增大的时候，这类算法的时间消耗增速很快，因此，要尽可能将设计算法的时间效率保证在 $n^3$ 以下

非递归算法效率分析

eg.

算法 MaxElement(A[0,1,...,n-1])

// 求出给定数组中的最大元素
// 输入：实数数组 A[0,1,...,n-1]
// 输出：A 中的最大元素

maxval ⬅ A[0]
for i ⬅ 1 to n-1 do
    if A[i] > maxval
        maxval ⬅ A[i]
return maxval

输入规模：数组长度 n

基本操作：比较运算

算法的效率：$C(n) = \sum_{i=1}^{n-1}1 = n-1 \in \Theta (n)$

非递归算法分析通用方案：

决定用那些参数作为输入规模的度量
找出算法的基本操作
检查基本操作的执行次数是否只依赖输入规模
建立一个算法基本操作执行次数的求和表达式
利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数

eg.

算法 UniqueElements(A[0,1,...,n-1])

// 验证给定数组的元素是否全部唯一
// 输入：实数数组 A[0,1,...,n-1]
// 输出：如果唯一，返回 True，否则 False

for i ⬅ 0 to n-2 do
    for j ⬅ i+1 to n-1 do
        if A[i] = A[j] return False
return True

输入规模：数组个数 n

基本操作：比较运算

算法的效率：$C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2} (n-i-1) = \frac{n(n-1)}{2}$

该算法最坏情况：$O(n^2)$

该算法最好情况：$\Omega (1)$

一般情况下：需要考虑数组中各种元素出现的情况，很难使用数学表达，因此很难确定一个具体的时间表达式，但从最坏的情况来看，该算法的时间上界为：$O (n^2)$

结论：

如果一个算法在执行过程中会根据条件终止，那么该算法会存在最优效率和最差效率，这时选择的时间渐进符号为：$\Omega$ 和 $O$，否则选择符号 $\Theta$

递归算法效率分析

eg.

算法 F(n)

// 递归计算 n!
// 输入：非负整数 n
// 输出：n! 的值

if n=0 return 1
else return F(n-1)*n

输入规模：n

基本操作：乘法

只有在递归调用的过程中才会多次执行基本操作

递归算法很难通过递归调用确定执行次数，但是可以根据递归调用的式子获取基本操作执行次数的递推式和初始条件，通过递推式的计算，得出递归算法的时间多项式

假设 M(n) 是输入规模为 n 时基本操作的执行次数，而在递归调用中的输入规模是 n-1，则递归调用过程中的基本操作执行次数可用 M(n-1) 来表示，M(n) 和 M(n-1) 之间刚好相差了 1 次乘法，即在递归调用中的乘法

基本操作执行次数递推式 $\Rightarrow$ $M(n) = \left\{\begin{matrix} M(n-1)+1 , \; n \geq 1 \\ \;\;\;\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\; ,\; n=0 \end{matrix}\right.$

$\Rightarrow$ $M(n) = M(n-1)+1$

$= [M(n-2)+1]+1 = M(n-2)+2$

$……$

$=[M(n-n)+1]+n-1=n$

递归算法分析通用方案

决定用哪个参数作为输入规模的度量
找出算法的基本操作
检査对相同规模的输入，基本操作的执行次数是否相同，如果不同，必须对最差、平均及最优效率单独研究
建立一个递推关系式及相应的初始条件
求解这个递归关系式，或者至少确定解的增长次数

TUFZ's Blog

认识算法分析

什么是算法？

算法分析？

时间渐进表示

非递归算法效率分析

递归算法效率分析