大学《数据结构》第一章：概论-第三节-算法的描述与分析

第三节算法的描述与分析一、算法的描述算法：是对问题求解步骤的一种描述。算法是由若干条指令组成的有穷序列，其中每条指令表示一个或多个操作。算法还必须满足以下五个准则：（1）输入。算法开始前必须给算法中用到的变量初始化，一个算法的输入可以包含零个或多个数据。（2）输出。算法至少有一个或多个输出。（3）有穷性。算法中每一条指令的执行次数都是有限的，而且每一步都在有穷时间内完成，即算法必须在执行有限步后结束。（4）确定性。算法中每一条指令的含义都必须明确，无二义性。（5）可行性。算法是可行的，即算法中描述的操作都可以通过有限次的基本运算来实现。本教材都采用类C语言描述算法。真题选解（例题·单选题）算法指的是()A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列隐藏答案【答案】D【解析】是对问题求解步骤的一种描述。算法是由若干条指令组成的有穷序列，它必须满足有穷性，即在执行有限步骤以后必须结束。二、算法分析例：百钱百鸡问题。100个钱买100只鸡，其中公鸡5钱1只，母鸡3钱1只，小鸡1钱3只，求公鸡、母鸡、小鸡各买多少只？分析：设公鸡、母鸡、小鸡分别买a、b、c只，则//函数返回值为满足问题的解数，g[]，m[]，s[]分别存放不同解的公鸡、母鸡和小鸡数intchickenquestion(intg[]，intm[]，ints[]){inta，b，c，k=0；for(a=0；a<=100；a++)for(b=0；b<=100；b++)for(c=0；c<=100；c++)if((a+b+c==100)&&(5*a+3*b+c/3==100)&&(c％3==0)){g[k]=a；m[k]=b；s[k]=c；k=k+1；}returnk；}算法需要执行101×101×101约100万次对上述算法是完全可以改进的。intchickenquestion(intg[]，intm[]，ints[]){inta，b，c，k=0；for(a=0；a<=20；a++)for(b=0；b<=33；b++){c=100-a-b；if((5*a+3*b+c/3==100)&&(c％3==0)){g[k]=a；m[k]=b；s[k]=c；k=k+1；}}returnk；}算法需要执行21×34=714次。因此，设计一个好的算法，对提高程序的执行效率是至关重要的。1、评价算法的指标：（1）算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果。（2）执行算法所耗费的时间，即时间复杂性。（3）执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性。（4）算法应易于理解、易于编程，易于调试等，即可读性和可操作性。2、算法的时间复杂度时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。记作T（n）=O（f（n））。例：求下面程序段的算法时间复杂度。x=0；for(i=2；i<=n；i++)for(j=2；j<=i-l；j++)x=x+1；算法时间复杂度只需要求出它关于n的增长率或阶即可。上述语句x=x+l执行次数关于n的增长率为n2，所以该程序段的算法时间复杂度为O(n2)。如果一个算法的执行时间是一个与"问题规模"无关的常数，即使是一个较大的常数，该算法的时间复杂度都为常数阶，记作T(n)=O(1)例：y=10000；while(y>0)y--；该程序段的时间复杂度就是O(1)时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。真题选解（例题·填空题）1、下面程序段的时间复杂度为___________。sum=1；for（i=0；sum<n;i++）sum+=1；隐藏答案【解析】循环执行n次，所以算法的时间复杂度为O（n）。【答案】O（n）（例题·填空题）2、估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。隐藏答案【答案】输入量【解析】时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模n的函数。将算法所要求解问题的输入量称为问题的规模。（例题·单选题）3、若一个算法的时间复杂度用T(n)表示，其中n的含义是（）A．问题规模B．语句条数C．循环层数D．函数数量隐藏答案【答案】A【解析】时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模n的函数。记作T（n）=O（f（n））。3、空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。4、算法复杂度：算法的时间复杂度和空间复杂度合称算法复杂度。当前讲授本