第二章-算法分析基础

算法分析的任务:对设计出的每一个具体的算法,利用数学工具，探讨其困难度。2.1算法分析体系及计量对算法的评价有两个大的方面：一.对算法的维护的便利性。二.算法在实现运行时占有的机器资源的多少,即算法的运行的时间和空间效率。2.1.1算法分析的评价体系

对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量及占用存储空间等诸多因素。其中评价算法的三条主要标准是：(1)算法实现所耗费的时间；(2)算法实现所所耗费的存储空间，其中主要考虑协助存储空间；(3)算法应易于理解，易于编码，易于调试等等。1.和算法执行时间相关的因素：1）问题中数据存储的数据结构2）算法接受的数学模型3）算法设计的策略

4）问题的规模

5）实现算法的程序设计语言

6）编译算法产生的机器代码的质量

7）计算机执行指令的速度

2.1.2算法的时间困难性

2．算法效率的衡量方法通常有两种衡量算法效率的方法:1）事后统计法（有缺点，较少运用）2）事前分析估算法算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=Ο(f(n))称T(n)为算法的渐近时间困难度(AsymptoticTimeComplexity),简称时间困难度。Ο是数量级的符号。3．时间困难度估算因为：算法=限制结构+原操作(固有数据类型的操作)所以：算法的执行时间=原操作的执行次数*原操作的执行时间语句的频度指的是该语句重复执行的次数。一个算法转换为算法后所耗费的时间,除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。一个算法中全部语句的频度之和构成了该算法的运行时间。例如：for(j=1;j<=n;++j)for(k=1;k<=n;++k)++x；

语句“++x、k<=n、++k”的频度是n2，语句“j=1、k=1”的频度是1，语句“j<=n;++j”的频度是n。算法运行时间为：3*n2+2n+2。

常常从算法中选取一种对于所探讨的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数状况下是最深层次循环体内的语句中的原操作。例如：for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j];}该算法的基本操作是乘法操作,时间困难度为n3。

例:n2+n+1的时间困难度?解:与n2的数量级相等(该表达式当n足够大时约等于n2),这个算法的时间困难度为：T(n)=O(n2)。数量级相等是这样定义的,设f(n)是一个关于正整数n的函数,若存在一个常数C，使则称f(n)与g(n)是同数量级的函数。

上节下节算法(渐进)时间困难度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称此为指数级Ο(n!)称为阶乘级上节下节以上时间困难度级别是由低到高排列的,其随规模n的增长率，由图2-1可见一斑：图2-1T(n)与规模n的函数关系原则上一个算法的时间困难度,最好不要接受指数级和阶乘级的算法,而应尽可能选用多项式级或线性级等时间困难度级别较小的算法。对于较困难的算法，可将它分隔成简洁估算的几个部分，然后再利用“O"的求和原则得到整个算法的时间困难度。例：若算法的两个部分的时间困难度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，则总的时间困难度为：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))。

4．问题时间困难度的上界和下界略5.算法时间困难度的最好状况和最坏状况

我们要确定能反映出算法在各种状况下工作的数据集,选取的数据要能够反映、代表各种计算状况下的估算,包括最好状况下的时间困难度(Tmax)最坏状况下的时间困难度(Tmin)平均状况下的时间困难度(Tavg)最有实际价值的,是最坏状况下的时间困难性。算法的存储量包括：

1)输入数据所占空间:取决于问题本身,与算法无关2)算法本身所占空间:相对固定3)协助变量所占空间2.1.3算法的空间困难性

探讨算法的空间效率，只须要分析除输入和算法之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作,否则,它应当是规模的一个函数。算法的空间困难度是指算法在执行过程中所占协助存储空间的大小用S(n)表示。算法的空间困难度S(n)也可表示为:S(n)=Ο(g(n))表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。

NP完全性问题:属于“计算困难性”探讨的课题。计算困难性:就是用计算机求解问题的难易程度。度量标准：一.计算所需的步数或指令条数(这叫时间困难度)。二.计算所需的存储单元数量(这叫空间困难度)。上节下节2.1.4NP完全问题

问题的困难性和算法的困难性的区分：只就时间困难性说，算法的困难性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的困难性是指这个问题本身的困难程度。P类问题:就是全部困难度为多项式时间的问题的集合(易解的问题类,否则犯难解的问题)。例如:梵塔问题推销员旅行问题等NP问题:至今没有找到多项式时间算法解的一类问题,可以在多项式时间内验证一个解是否正确的问题,亦称为易验证问题类。

NP完全问题(NPC问题,C代表complete):从NP类的问题中分出困难性最高的一个子类。假如一个NPC问题存在多项式时间的算法，则全部的NP问题都可以在多项式时间内求解，即P=NP成立!!要么每个NP完全问题都存在多项式时间的算法（即通常所指的有效算法）；要么全部NP完全问题都不存在多项式时间的算法。目前已知的NP完全问题就有2000多个,其中有很多是特别重要的问题,如:货郎问题、最大独立集问题、背包问题、装箱问题、…等等。

遇到这类问题时，通常从以下几个方面来考虑并寻求解决方法:1)特殊情形特殊方法2)动态规划和分枝限界方法3)概率分析4)近似算法5)启发式算法上节下节一具体算法的时间困难度和空间困难度往往是不独立的，在算法设计中要在时间效率和空间效率之间折衷。

2.2算法分析实例

1．仅依靠于问题规模的时间困难度有一类简洁的问题，其操作具有普遍性，也就是说对全部的数据均等价地进行处理，这类算法的时间困难度，很简洁分析。

2.2.1非递归算法分析【例1】交换i和j的内容。Temp=i；i=j；j=temp；以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间困难度为常数阶，记作T(n)=Ο(1)。假如算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间困难度是Ο(1)。上节下节【例2】循环次数干脆依靠规模n(1)x=0；=0；(2)for(k-1；<=n；++)(3)x++；(4)for(i=1；<=n；++)(5)for(j=1；j<=n；++)(6)y++；T(n)=Ο(n2)。当有若干个循环语句时，算法的时间困难度是由嵌套层数最多的循环语句中最内层语句的频度f(n)确定的。上节下节y++【例3】循环次数间接依靠规模n(1)x=1；(2)for(i=1；i<=n；i++)(3)for(j=1；j<=i；j++)(4)for(k=1；k<=j；k++)(5)x++；该算法段中频度最大的语句是(5)，从内层循环向外层分析语句(5)的执行次数：则该算法段的时间困难度为：T(n)=O(n3/6+低次项)=O(n3)。2.算法的时间困难度还与输入实例的初始状态有关。

这类算法的时间困难度的分析比较困难，一般分最好状况（处理最少的状况),最坏状况(处理最多的状况)和平均状况分别进行探讨。【例4】【例4】在数值A[0..n-1]中查找给定值K的算法大致如下：(1)i=n-1；(2)while(i>=0andA[i]<>k)(3)i=i-1；(4)returni；

此算法的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及k的取值有关：1.若A中没有与k相等的元素，则语句(2)的频度f(n)=n；这是最坏状况。2.若A的最终一个元素等于k,则语句(2)的频度f(n)是常数1;这是最好状况。在求平均状况时，一般地假设查找不同元素的概率P是相同的,则算法的平均困难度为：若对于查找不同元素的概率P不相同时，其算法困难度就只能做近似分析，或在构造更好的算法或存储结构后，做较精确的分析。上节下节2.2.2递归算法分析

【例1】求N！构造算法中的两个步骤：1）N!=N*(N-1)！2）0!=1，1!=1。

递归算法如下：

以n=3为例,调用过程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)递归回溯迭代法介绍：用迭代方法估计递归算法的解,就是充分利用递归算法中的递归关系,通过确定的代数运算和数学分析的级数学问,得到问题的困难度。递归方程具体就是利用递归算法中的递归关系写出递归方程,迭代地绽开的右端，使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解的估计。上节下节

【例1】求n!递归方程为：T(n)=T(n-1)+O(1)其中O(1)为一次乘法操作.

迭代求解过程如下：T(n)=T(n-2)+O(1)+O(1)=T(n-3)+O(1)+O(1)+O(1)……=O(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)

【例2】抽象地考虑以下困难一点的递归方程，且假设n=2k，则迭代求解过程如下：=O(n)

一般地，当递归方程为：T（n）=aT（n/c）+O(n)，T（n）的解为：①O(n)a<c且c>1时②O(nlogcn)a=c且c>1时③O(nlogca)a>c且c>1时在满足正确性、牢靠性、健壮性、可读性等质量因素的前下，设法提高算法的效率。看两组操作：(1)a=a+b；b=a-b；a=a-b；(2)t=a；a=b；b=t；

2.2.3提高算法质量两组操作的功能都是：“交换变量a、b中的数据”。虽然第一组操作节约了一个存储空间，但失去了可读性，是不行取的。下面给出一些原则上的建议：