算法的效率

发布时间:2019-07-04 作者:大扑棱蛾子 阅读次数:
版权声明:未经允许不得转载至微信公众号,转载至个人博客请注明出处。 阅读原文

效率是速度和空间消耗的度量。也称运行时间或执行时间的测定,并描述速度的一般定量的标准。这一标准就是负责度的并用大写字母OO表示,读作大OO

多项式的算数运算

多元组表示
可以用多项式系数的有序多元组来表示多项式,多元组的长度等于这个多项式的次数加1。

4x52x3+2x+3(4,0,2,0,2,3)\begin{array}{cc} 4x^5-2x^3+2x+3\\ (4,\enspace 0,\enspace -2,\enspace 0,\enspace 2,\enspace 3) \end{array}

加法/减法

在纸上对两个多项式进行加运算是,把它们一上一下的排列起来,使得次数相同的项的系数处于相同的列:

P1=+4x5+2x3+2x+3P2=+8x4+4x33x+9P1+P2=+4x5+8x4+2x3x+12\begin{aligned} P_1& = &+ 4x^5 && +2x^3 & +2x & +3\\ P_2& = &&+ 8x^4 & +4x^3 & -3x & +9\\ \hline\\ P_1 + P_2&= & + 4x^5 & + 8x^4 & +2x^3 & -x & +12 \end{aligned}

使用元组表示法:

P1+P2=(4,0,2,0,2,3)+(0,8,4,0,3,9)=(4,8,2,0,1,12)\begin{aligned} P_1 + P_2&=(4,\> 0,\> -2,\> 0,\> 2,\> 3)+(0,\> 8,\>4,\>0,\>-3,\>9)\\ &=(4,\>8,\>2,\>0,\>-1,\>12) \end{aligned}

乘法

P1=3x2+x+2P2=x33P1P2=(3,1,2)(1,0,0,3)\begin{aligned} P_1& = 3x^2+x+2\\ P_2& = x^3-3\\ P_1 \cdot P_2&= (3,1,2)*(1,0,0,-3) \end{aligned}

通过把第一个多项式中的每一个系数与第二个多项式的每一个系数相乘,可以求得P1P_1P2P_2的乘积。

3121003936000000312312936\begin{array}{l} &&& 3 & 1 & 2\\ && 1 & 0 & 0 & -3\\ \hline\\ &&&-9 & -3 & -6\\ &&0 & 0 & 0\\ &0 & 0 & 0\\ 3 & 1 & 2\\ \hline 3&1&2&-9&-3&-6 \end{array}

最终这个两个多项式的乘积为3x5+x4+2x39x23x6\:3x^5+x^4+2x^3-9x^2-3x-6

求值与霍纳(horner)法则

假定求下面的多项式

p=4x42x3+5x2+10x15p=4x^4-2x^3+5x^2+10x-15

求平方其实就是乘法运算,2次方需要一次乘法即xxx\cdot x
所以总共需要(1+3)+(1+2)+(1+1)+1=4+3+2+1=10(1+3)+(1+2)+(1+1)+1=4+3+2+1=10次计算。
更好的方法是使用霍纳法则,避免重复的乘法,比如当已经计算好x3x^3时,再做一次乘法就可以得到x4:xx3x^4:x \cdot x^3

p=4x42x3+5x2+10x15=(4x32x2+5x+10)x15=((4x22x+5)x+10)x15=(((4x2)x+5)x+10)x15\begin{aligned} p&=4x^4-2x^3+5x^2+10x-15\\ &=(4x^3-2x^2+5x+10)x-15\\ &=((4x^2-2x+5)x+10)x-15\\ &=(((4x-2)x+5)x+10)x-15\\ \hline &\kern2.5em\uarr\kern2.4em\uarr\kern2.1em\uarr\kern2.5em\uarr \end{aligned}


基本操作

测定运行时间
测定运行时间的最可靠方法就是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。

下表中列举了一些基本操作的例子。

程序 基本操作
排序一组整数 比较两个整数
把一个文件复制到另一个文件 复制一个字节
把两个多项式相加 把两个系数相加
重要的是程序所实现的算法
在分析程序的运行时间时,重要的是把程序看成算法,即独立于实现它的程序设计语言的一系列步骤。

例子:多项式求值,在多项式求值中通常乘法比加法慢。因此,乘法是主导的基本操作。


输入规模

基本操作与输入规模
在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数。
算法 输入规模
排序 nn:要排序的整数的个数
文件复制 nn:输入文件中的字节数量
多项式加法 nn:第一个多项式的次数
mm:第二个多项式的次数

函数的渐近增长

假设存在两个如下两个算法AABB

A=3n10B=2n+10A = 3n-10\\ B = 2n+10

当n=20时,AABB的比较次数相等。当n>20n>20时,BB的比较次数小于AA的比较次数。即BBAA快(这里的快指运行时间,也可以理解为执行的基本操作次数少)。

显然,在比较次数中,重要的是与nn相乘的常数,而不是加或减的常数。因此,当作为nn的函数测定运行时间时,可以忽略这些加法常数。

函数的渐近增长
给定两个函数f(x)g(n)f(x) \text{和} g(n),如果存在一个整数NN,使得对于所有的n>Nn>Nf(n)f(n)总是比g(n)g(n)大,那么,我们就说f(n)f(n)的增长渐近快于g(n)g(n)

考虑两个执行相同任务的算法PPQQ

fp(n)=4n+20fq(n)=2n210\begin{array}{ll} f_p(n)=4n+20\\ f_q(n)=2n^2-10 \end{array}

nn fpf_p fqf_q
5 40 40
10 60 190
20 100 790
50 220 4990

显然与fpf_p相比较fqf_q是在跳跃式的增长。这是因为的fqf_q主导项是二次的,而fpf_p的主导项只是线性的(次数为1),即使前者的乘积常数比后者的小,fqf_q还是比fpf_p增长的快,在这种情况下,与主导项相乘的常数不重要。

PP的线性运行时间与QQ的二次运行时间属于不同的级别,或不同的复杂度的阶。我们说QQ的运行时间是n2n^2阶的,而PP的运行时间是nn阶的。


阶与大OO

在比较算法的运行时间时,重要的是确定运行时间去除了乘法常数和加法常数后的阶。有相同运行时间阶的算法被认为是处于相同的速度水平。记号OO成为大OO,是阶的一种简捷记法。因此,用O(n)O(n)表示“阶为nn”,用O(n2)O(n^2)表示“阶为n2n^2”。

OO

给定两个函数f(n)f(n)g(n)g(n)f(n)=O(g(n))f(n)=O(g(n))当且仅当存在一个常数cc使得cg(n)c*g(n)的增长渐近快于f(n)f(n)

假设f(n)=4n+20f(n)=4n+20g(n)=ng(n)=n。那么,对于c=5,cg(n)c=5,c*g(n)的增长渐近快于f(n)f(n),所以,f(n)=4n+20=O(n)f(n)=4n+20=O(n)。换句话说,4n+204n+20是阶nn的(或它的阶是nn)。

推导大OO

  1. 用常数1取代运行时间中所有的加法常数(减法可以理解为加一个负数)。
  2. 在修改后的运行时间中,只保留最高阶项
  3. 如果最高阶项不是1,去除与这个项相乘的常数。剩下的就是大OO

求多项式的阶

多项式求值P=anxn+an1xn1+an2xn2+...+a3x3+a2x2+a1xP=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{3}x^{3}+a_{2}x^{2}+a_{1}x

在多项式的计算中通常乘法比加法慢。因此,乘法是主导的基本操作。假设有一个次数为nn的多项式,并且各项系数均不为0。

常规解法
使用常规解法就必须求下列各幂的值。

xn,  xn1,  xn+2,  xn3,  ...  ,  x3,  x2,  x1x^n,\;x^{n-1},\;x^{n+2},\;x^{n-3},\;...\;,\;x^3,\;x^2,\;x^1

第一项执行n1n-1次乘法,第二项是n2n-2以此类推,执行乘法的总数是

(n1)+(n2)+(n3)+...+3+2+1=n(n1)2=n22n2(n-1)+ (n-2) + (n-3) + ... + 3 + 2 + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}

除常数外,每项需要与系数的一次乘法,总共是nn次,因此总的乘法次数是

n22n2+n=n22+n2\frac{n^2}{2} - \frac{n}{2} + n = \frac{n^2}{2} + \frac{n}{2}

根据上面的步骤推导出大OO的阶为n2n^2

使用霍纳法则
使用霍纳法则求值多项式,只需要进行nn此乘法即可,所以说运行时间是O(n)O(n)

典型运行时间的阶

典型的运行时间的阶有:常数阶、线性阶、二次阶、对数阶、三次阶、指数阶。

运行时间 非正式术语
10 O(1)O(1) 常数
3n+253n+25 O(n)O(n) 线性
1.5n2+25n551.5n^2+25n-55 O(n2)O(n^2) 二次
250n+10nlogn+25250n+10n\log{n} + 25 O(nlogn)O(n\log{n}) enlogenen\quad log \quad en
3logn+303\log{n}+30 O(logn)O(\log{n}) 对数
10n3+2n10n^3+2n O(n3)O(n^3) 三次
122n12 * 2^n O(kn)O(k^n) 指数

阶的相对顺序

1<logn<n<n<nlogn<nn<n2<n3<kn1 < \log{n} < \sqrt{n} < n < n\log{n}< n\sqrt{n}<n^2<n^3<k^n

阶的算术运算

阶函数中的变量
对于出现在算法输入规模中的每一个变量,算法的运行时间的阶函数中至多有一项包含该变量。

O(n+nlogn)O(n + n\log{n}),因为项nlognn\log{n}是主导项,所以应该写成O(nlogn)O(n\log{n}),类似的如O(n+n2)O(n + n^2)应写为O(n2)O(n^2)


最坏情况与平均情况

复杂度的最坏情况
通常,计算机科学家使用“时间复杂度”指运算时间需求,并使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,他们通常指时间复杂度。另外,如果他们没有特指平均情况或最坏情况,一般指的是最坏情况。

一个算法的空间需求总是小于或等于它的时间需求。

评论

Power by 不蒜子
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×