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

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

1 算法的两种时间复杂度

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

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

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

A ( n ) = <munder> I S </munder> P I t I A(n) = \sum_{I{\in}S} P_It_I A(n)=ISPItI

其中:S为规模为n的实例集,实例 I S I\in S IS的概率为PI .算法对实例I执行的基本运算次数为:tI

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

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次比较。
  1. 平均情况的时间估计

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

A ( n ) = <munderover> i = 1 n </munderover> i p n + ( 1 p ) n = p ( n + 1 ) 2 + ( 1 p ) n A(n) = \sum_{i=1}^n i\frac{p}{n} + (1-p)n = \frac{p(n+1)}{2}+(1-p)n A(n)=i=1ninp+(1p)n=2p(n+1)+(1p)n

当p=1/2时, A ( n ) = n + 1 4 + n 2 3 n 4 A(n)=\frac{n+1}{4}+\frac{n}{2} \approx \frac{3n}{4} A(n)=4n+1+2n43n

注意:上述求解公式中,注意理解(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。则 p n = 1 p n + 1 \frac{p}{n}=\frac{1-p}{n+1} np=n+11p

则由公式,计算平均时间复杂度为:

A ( n ) = <munderover> i = 1 n </munderover> i p n + 1 p n + 1 n = <munderover> i = 1 n </munderover> i p n + p n n A(n) = \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=1ninp+n+11pn=i=1ninp+npn
= p ( 1 + n ) 2 + p =\frac{p(1+n)}{2}+p =2p(1+n)+p

当p=1/2时:

A ( n ) = n 4 + 3 4 n 4 A(n)=\frac{n}{4}+\frac{3}{4} \approx \frac{n}{4} A(n)=4n+434n

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

2 总结

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