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

Myth丶恋晨 2021-12-20 10:35 365阅读 0赞

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

### 文章目录 ###

*   *  1 算法的两种时间复杂度
     *   *  1.1 例子：检索问题
         *   *  (1)顺序检索算法
             *  (2)改进顺序检索算法
     *  2 总结

## 1 算法的两种时间复杂度 ##

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

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

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

A ( n ) = ∑ I ∈ S P I t I A(n) = \\sum\_\{I\{\\in\}S\} P\_It\_I A(n)=I∈S∑PItI

其中：S为规模为n的实例集，实例 I ∈ S I\\in S I∈S的概率为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个，分别对应：  
![在这里插入图片描述][20190628194834963.png_pic_center]

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

1.  平均情况的时间估计

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

A ( n ) = ∑ i = 1 n 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=1∑ninp\+(1−p)n=2p(n\+1)\+(1−p)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\+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。则 p n = 1 − p n + 1 \\frac\{p\}\{n\}=\\frac\{1-p\}\{n+1\} np=n\+11−p

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

A ( n ) = ∑ i = 1 n i p n + 1 − p n + 1 n = ∑ i = 1 n 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=1∑ninp\+n\+11−pn=i=1∑ninp\+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\+43≈4n

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

## 2 总结 ##

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

[20190628194834963.png_pic_center]: /images/20211220/435cb35ce72e4541ab76f4c475d3c68a.png