【算法设计与分析】03 算法及其时间复杂度

在学习算法的时间复杂度之前，需要了解下面5条概念

• 什么是算法的时间复杂度？ 针对指定基本运算，计数算法所做的运算次数。
• 什么是基本运算？比较、加法、乘法、置指针、交换…
• 什么是输入规模？输入串的编码长度，通常是数组元素的多少、调度问题的任务个数、图的顶点数与边数等。
• 算法的基本运算次数可以表示为输入规模的函数。
• 给定问题和基本运算，就决定了一个算法类

1 算法的两种时间复杂度

对于相同输入规模的不同实例，算法的基本运算次数也不一样，所以定义了两种时间复杂度。

1. 最坏情况下的时间复杂度W(n):算法求解输入规模为n的实例所需要最长的时间
2. 平均情况下的时间复杂度A(n): 在给定同样规模为n的实例的概率分布下，算法求解这些实例所需要的平均时间。

平均情况下的时间复杂度求解公式为：

$A\left(n\right)=\sum _{I\in S}{P}_I{t}_I$A(n)=I∈S∑​PI​tI​

其中：S为规模为n的实例集，实例 $I\in S$I∈S的概率为P_I .算法对实例I执行的基本运算次数为：t_I

在某些情况下，可以假定每个输入实例的概率相等。

1.1 例子：检索问题

• 输入：非降序排列的数组L，元素个数n，需要检索的数x。
• 输出：j。如果x在数组L中，j是x首次出现的下标。否则j=0.
• 基本运算：x与L中的元素比较。

(1)顺序检索算法

j=1, 将x与L[j]比较. 如果 x=L[j]，则算法停止，输出 j；如果不等，则把 j 加1，继续x与L[j]的比较，如果 j>n，则停机并输出0。

实例：1 2 3 4 5
x=4，需要比较4次
x=2.5 ，需要比较5次

1. 最坏情况时间复杂度

不同的输入有:2n+1个，分别对应：

• 最坏情况下时间：W(n)=n；
• 最坏的输入：x不在L中，或者x=L[n]（还没有接触到数据结构中的数组，下表不是从0开始的，是从1开始的）。此时要做n次比较。

2. 平均情况的时间估计

输入实例的概率分布：假设x在L中的概率是P，且每个位置的概率相等。则由上文的公式得：

$A\left(n\right)=\sum _{i=1}^{n}i\frac{p}{n}+(1-p)n=\frac{p(n+1)}{2}+(1-p)n$A(n)=i=1∑n​inp​+(1−p)n=2p(n+1)​+(1−p)n

当p=1/2时， $A\left(n\right)=\frac{n+1}{4}+\frac{n}{2}\approx \frac{3n}{4}$A(n)=4n+1​+2n​≈43n​

注意：上述求解公式中，注意理解(1-p)n 代表如果元素不存在数组中，比较的次数是从头到尾。即n次，不存在的概率是1-p。

(2)改进顺序检索算法

j=1, 将 x与L[j]比较. 如果 x=L[j]，则算法停止，输出 j；如果 x >L[j]，则把 j 加1，继续 x与 L[j]的比较；如果 x < L[j]，则停机并输出0. 如果 j >n，则停机并输出 0。

之所以可以优化成这样是因为该算法的输入是：非降序排列的数组

实例：1 2 3 4 5
x = 4，需要比较 4 次
x = 2.5，需要比较 3 次

1. 最坏情况时间复杂度：W(n) = n
2. 平均情况时间复杂度

输入实例的概率分布：假设x在数组L中的每个位置与空隙的概率都相等。设在数组中的概率是p，不在数组L中的概率是1-p。则 $\frac{p}{n}=\frac{1-p}{n+1}$np​=n+11−p​

则由公式，计算平均时间复杂度为：

$A\left(n\right)=\sum _{i=1}^{n}i\frac{p}{n}+\frac{1-p}{n+1}n=\sum _{i=1}^{n}i\frac{p}{n}+\frac{p}{n}n$A(n)=i=1∑n​inp​+n+11−p​n=i=1∑n​inp​+np​n
$=\frac{p(1+n)}{2}+p$=2p(1+n)​+p

当p=1/2时：

$A\left(n\right)=\frac{n}{4}+\frac{3}{4}\approx \frac{n}{4}$A(n)=4n​+43​≈4n​

很明显，改进后的检索算法，时间复杂度减小了很多。算法的性能有所提升。

2 总结

• 本文的学习并不是来学习检索这个算法也不是来提升它的性能。
• 而是根据检索算法这个例子，来学习时间复杂度的定义，学会计算时间复杂度。