-
Notifications
You must be signed in to change notification settings - Fork 25
/
ch11s03.html
15 lines (15 loc) · 10.1 KB
/
ch11s03.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>3. 算法的时间复杂度分析</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch11.html" title="第 11 章 排序与查找" /><link rel="prev" href="ch11s02.html" title="2. 插入排序" /><link rel="next" href="ch11s04.html" title="4. 归并排序" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">3. 算法的时间复杂度分析</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s02.html">上一页</a> </td><th width="60%" align="center">第 11 章 排序与查找</th><td width="20%" align="right"> <a accesskey="n" href="ch11s04.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2745574"></a>3. 算法的时间复杂度分析</h2></div></div></div><p>解决同一个问题可以有很多种算法,比较评价算法的好坏,一个重要的标准就是算法的时间复杂度。现在研究一下插入排序算法的执行时间,按照习惯,输入长度<code class="literal">LEN</code>以下用n表示。设循环中各条语句的执行时间分别是c1、c2、c3、c4、c5这样五个常数<sup>[<a id="id2745592" href="#ftn.id2745592" class="footnote">23</a>]</sup>:</p><pre class="programlisting">void insertion_sort(void) 执行时间
{
int i, j, key;
for (j = 1; j < LEN; j++) {
key = a[j]; c1
i = j - 1; c2
while (i >= 0 && a[i] > key) {
a[i+1] = a[i]; c3
i--; c4
}
a[i+1] = key; c5
}
}</pre><p>显然外层<code class="literal">for</code>循环的执行次数是n-1次,假设内层的<code class="literal">while</code>循环执行m次,则总的执行时间粗略估计是(n-1)*(c1+c2+c5+m*(c3+c4))。当然,<code class="literal">for</code>和<code class="literal">while</code>后面()括号中的赋值和条件判断的执行也需要时间,而我没有设一个常数来表示,这不影响我们的粗略估计。</p><p>这里有一个问题,m不是个常数,也不取决于输入长度n,而是取决于具体的输入数据。在最好情况下,数组<code class="literal">a</code>的原始数据已经排好序了,<code class="literal">while</code>循环一次也不执行,总的执行时间是(c1+c2+c5)*n-(c1+c2+c5),可以表示成an+b的形式,是n的线性函数(Linear Function)<a id="id2745665" class="indexterm"></a>。那么在最坏情况(Worst Case)<a id="id2745673" class="indexterm"></a>下又如何呢?所谓最坏情况是指数组<code class="literal">a</code>的原始数据正好是从大到小排好序的,请读者想一想为什么这是最坏情况,然后把上式中的m替换掉算一下执行时间是多少。</p><p>数组<code class="literal">a</code>的原始数据属于最好和最坏情况的都比较少见,如果原始数据是随机的,可称为平均情况(Average Case)<a id="id2745700" class="indexterm"></a>。如果原始数据是随机的,那么每次循环将已排序的子序列a[1..j-1]与新插入的元素<code class="literal">key</code>相比较,子序列中平均都有一半的元素比<code class="literal">key</code>大而另一半比<code class="literal">key</code>小,请读者把上式中的m替换掉算一下执行时间是多少。最后的结论应该是:在最坏情况和平均情况下,总的执行时间都可以表示成an<sup>2</sup>+bn+c的形式,是n的二次函数(Quadratic Function)<a id="id2745736" class="indexterm"></a>。</p><p>在分析算法的时间复杂度时,我们更关心最坏情况而不是最好情况,理由如下:</p><div class="orderedlist"><ol type="1"><li><p>最坏情况给出了算法执行时间的上界,我们可以确信,无论给什么输入,算法的执行时间都不会超过这个上界,这样为比较和分析提供了便利。</p></li><li><p>对于某些算法,最坏情况是最常发生的情况,例如在数据库中查找某个信息的算法,最坏情况就是数据库中根本不存在该信息,都找遍了也没有,而某些应用场合经常要查找一个信息在数据库中存在不存在。</p></li><li><p>虽然最坏情况是一种悲观估计,但是对于很多问题,平均情况和最坏情况的时间复杂度差不多,比如插入排序这个例子,平均情况和最坏情况的时间复杂度都是输入长度n的二次函数。</p></li></ol></div><p>比较两个多项式a<sub>1</sub>n+b<sub>1</sub>和a<sub>2</sub>n<sup>2</sup>+b<sub>2</sub>n+c<sub>2</sub>的值(n取正整数)可以得出结论:n的最高次指数是最主要的决定因素,常数项、低次幂项和系数都是次要的。比如100n+1和n<sup>2</sup>+1,虽然后者的系数小,当n较小时前者的值较大,但是当n>100时,后者的值就远远大于前者了。如果同一个问题可以用两种算法解决,其中一种算法的时间复杂度为线性函数,另一种算法的时间复杂度为二次函数,当问题的输入长度n足够大时,前者明显优于后者。因此我们可以用一种更粗略的方式表示算法的时间复杂度,把系数和低次幂项都省去,线性函数记作Θ(n),二次函数记作Θ(n<sup>2</sup>)。</p><p>Θ(g(n))表示和g(n)同一量级的一类函数,例如所有的二次函数f(n)都和g(n)=n<sup>2</sup>属于同一量级,都可以用Θ(n<sup>2</sup>)来表示,甚至有些不是二次函数的也和n<sup>2</sup>属于同一量级,例如2n<sup>2</sup>+3lgn。“<span class="quote">同一量级</span>”这个概念可以用下图来说明(该图出自<a class="xref" href="bi01.html#bibli.algorithm" title="Introduction to Algorithms">[<abbr class="abbrev">算法导论</abbr>]</a>):</p><div class="figure"><a id="id2745857"></a><p class="title"><b>图 11.2. Θ-notation</b></p><div class="figure-contents"><div><img src="images/sortsearch.theta.png" alt="Θ-notation" /></div></div></div><br class="figure-break" /><p>如果可以找到两个正的常数c<sub>1</sub>和c<sub>2</sub>,使得n足够大的时候(也就是n≥n<sub>0</sub>的时候)f(n)总是夹在c<sub>1</sub>g(n)和c<sub>2</sub>g(n)之间,就说f(n)和g(n)是同一量级的,f(n)就可以用Θ(g(n))来表示。</p><p>以二次函数为例,比如1/2n<sup>2</sup>-3n,要证明它是属于Θ(n<sup>2</sup>)这个集合的,我们必须确定c<sub>1</sub>、c<sub>2</sub>和n<sub>0</sub>,这些常数不随n改变,并且当n≥n<sub>0</sub>以后,c<sub>1</sub>n<sup>2</sup>≤1/2n<sup>2</sup>-3n≤c<sub>2</sub>n<sup>2</sup>总是成立的。为此我们从不等式的每一边都除以n<sup>2</sup>,得到c<sub>1</sub>≤1/2-3/n≤c<sub>2</sub>。见下图:</p><div class="figure"><a id="id2745950"></a><p class="title"><b>图 11.3. 1/2-3/n</b></p><div class="figure-contents"><div><img src="images/sortsearch.fn0.png" alt="1/2-3/n" /></div></div></div><br class="figure-break" /><p>这样就很容易看出来,无论n取多少,该函数一定小于1/2,因此c<sub>2</sub>=1/2,当n=6时函数值为0,n>6时该函数都大于0,可以取n<sub>0</sub>=7,c<sub>1</sub>=1/14,这样当n≥n<sub>0</sub>时都有1/2-3/n≥c<sub>1</sub>。通过这个证明过程可以得出结论,当n足够大时任何an<sup>2</sup>+bn+c都夹在c<sub>1</sub>n<sup>2</sup>和c<sub>2</sub>n<sup>2</sup>之间,相对于n<sup>2</sup>项来说bn+c的影响可以忽略,a可以通过选取合适的c<sub>1</sub>、c<sub>2</sub>来补偿。</p><p>几种常见的时间复杂度函数按数量级从小到大的顺序依次是:Θ(lgn),Θ(sqrt(n)),Θ(n),Θ(nlgn),Θ(n<sup>2</sup>),Θ(n<sup>3</sup>),Θ(2<sup>n</sup>),Θ(n!)。其中,lgn通常表示以10为底n的对数,但是对于Θ-notation<a id="id2746036" class="indexterm"></a>来说,Θ(lgn)和Θ(log<sub>2</sub>n)并无区别(想一想这是为什么),在算法分析中lgn通常表示以2为底n的对数。可是什么算法的时间复杂度里会出现lgn呢?回顾插入排序的时间复杂度分析,无非是循环体的执行时间乘以循环次数,只有加和乘运算,怎么会出来lg呢?下一节归并排序的时间复杂度里面就有lg,请读者留心lg运算是从哪出来的。</p><p>除了Θ-notation之外,表示算法的时间复杂度常用的还有一种Big-O notation<a id="id2746061" class="indexterm"></a>。我们知道插入排序在最坏情况和平均情况下时间复杂度是Θ(n<sup>2</sup>),在最好情况下是Θ(n),数量级比Θ(n<sup>2</sup>)要小,那么总结起来在各种情况下插入排序的时间复杂度是O(n<sup>2</sup>)。Θ的含义和“<span class="quote">等于</span>”类似,而大O的含义和“<span class="quote">小于等于</span>”类似。</p><div class="footnotes"><br /><hr width="100" align="left" /><div class="footnote"><p><sup>[<a id="ftn.id2745592" href="#id2745592" class="para">23</a>] </sup>受内存管理机制的影响,指令的执行时间不一定是常数,但执行时间的上界(Upper Bound)<a id="id2745597" class="indexterm"></a>肯定是常数,我们这里假设语句的执行时间是常数只是一个粗略估计。</p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s02.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch11s04.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">2. 插入排序 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 4. 归并排序</td></tr></table></div></body></html>