3--1-2 算法及其描述C君带你玩编程

算法及其描述来源普运伟主编《大学计算机一面向实践与创新能力培养》，人民邮电出版社，2016程序设计要遵循一定的步骤，计算机求解问题的关键在于算法设计算法的设计与实现是客观世界向抽象世界转化，并由抽象世界步入计算机世界的过程1算法的定义算法Algorithm就是指为解决一个具体问题而采取的方法和步骤的集合在日常的学习和生活中，算法的例子随处可见求解一道数学应用题，要有清晰的思路和明确的步骤；使用《新华字典》查询一个生字，也要讲究是采用拼音检字法还是部首检字法，甚或是直接查询法等，这些都是算法的实例如果要编制程序让计算机帮助我们解决一个实际的问题，同样需要考虑解决问题的算法不难想象，一个好的算法可以很快得到待解决问题的答案，一个不好的算法却要耗费更多的时间和资源，而一个错误的算法则根本无法得到正确的结果可见，正如著名计算机科学家Niklaus Wirth所言算法是程序设计的灵魂，程序设计的关键在于算法2算法的基本特征算法是一个有穷规则的集合，这些规则确定了解决问题的一个运算序列使用计算机程序求解问题，要有一个明确的起点，确定的步骤序列，程序终止执行时要能给出最后的结果因此,一个算法应具备如下五个重要特征

①输入0或多个输入，其中0输入表示算法本身已给出初始条件

②输出1或多个输出，没有输出的算法是毫无意义的3有穷性算法的执行步骤是有限的，且每一步骤的执行时间是可容忍的4确定性算法的每一步骤具有确切的含义，不允许出现歧义5可行性算法的每一步操作都可以通过已经实现的基本运算执行有限次数来实现需要说明的是，一个实用的算法不仅要求有穷的操作步骤，而且应该是尽可能有限的步骤例如，对线性方程组求解，理论上可以用行列式的方法但是要对n阶方程组求解，需要计算n+1个n阶行列式的值，要做的乘法运算是n!n-1n+1次假如n取值为20,用每秒千万次的计算机运算，完成这个计算需要上千万年的时间可见，尽管这种算法是正确的，但它没有实际意义由此可知，在设计算法时，要对算法的执行效率作一定的分析3算法的表示在算法的设计过程中，有必要将算法的主要步骤清晰地记录和表示出来，这不仅有利于编程者之间相互交流所设计算法的主要思路，而且有利于算法后期的改进和优化常见的算法表示方法有自然语言、伪代码、流程图、N-S图和PAD图等，下面择其部分进行简要介绍

①自然语言表示法自然语言表示法就是使用人们日常所用的语言如汉语或英语等对算法进行描述例如,要将一杯水和一杯牛奶进行交换，由于杯子里装满了水和牛奶，无法直接进行交换，需借助第三个空的杯子因此，算法可描述如下第一步，将水从杯子1中倒入杯子3中第二步，将牛奶从杯子2中倒入杯子1中第三步，将水从杯子3中倒回杯子2中可见，自然语言描述方法通俗易懂，但较为繁琐，且容易产生歧义

②伪代码表示法伪代码是一种人们交流过程中使用的非正式表述方法，通常采用自然语言、数学公式和符号混合使用来描述算法的步骤，同时采用计算机高级语言的控制结构来描述算法的执行顺序可见,伪代码是一种虚拟代码，介于自然语言和计算机语言之间，它兼有自然语言通俗易懂的优点，同时又因部分使用计算机高级语言而避免了歧义性，因此是非正式场合广泛使用的一种算法描述方法例如，要判断一个四位数组成的年份是否为闰年判断方法是如果该年份能被4整除但不能被100整除，或者能被400整除，则该年为闰年，即该年份的2月有29天对这一方法用伪代码可表示如下BEGIN（算法开始）输入年份yIF y能被4整除THENIF y不能被100整除THEN输出“y是闰年”ELSEIF y能被400整除THEN输出“y是闰年”ELSE输出“y不是闰年”END IFENDIFELSE输出“y不是闰年”END IFEND（算法结束）可见，伪代码类似自然语言，又有程序流程框架，易于理解和修改，也易于转化为程序语言代码，但缺点是不够直观

③流程图表示法流程图是一种采用程序框、流程线及简要文字说明来表示算法的有效方法其中，程序框图用于表示算法中的具体步骤，流程线表示算法的执行顺序流程图中常用的符号如表8-2所示表8-2流程图中常用的符号符号名称功能起止框表示算法的起始和结束，有时为了简化流程图也可省略LJ输入/输出框表示算法的输入和输出的信息O判断条件是否成立，成立时在出口处标明“是”或“Y”；判断框不成立时标明“否”或“N”赋值、计算算法中处理数据需要的算式、公式等分别写—处理框在不同的用以处理数据的处理框内流程线连接程序框，带有控制方向O连接点连接程序框的两部分例如，要取出两个数中的较大者，其算法流程图可表示为如图8-3所示图8-3输出两个数中最大者的算法流程图不难发现，前面“鸡兔同笼”问题中的算法描述方法如图8-2所示采用的也是流程图方法流程图作为一种直观的图形化表示方法，能够准确、清晰、形象地表示算法的流程和走向,因此得到了广泛应用作为一名程序设计者，要学会针对问题进行算法设计，并使用流程图对算法进行描述4算法的评价对于算法的评价有两个基本标准，即时间复杂度和空间复杂度所谓时间复杂度，就是执行这个算法需要多少时间实际上算法确切的执行时间不通过上机测试是无法得出的，一般认为一个算法花费的时间与算法中语句的执行次数成正比例算法的时间复杂度表示为Tn=Ofn,其中fn表示算法中基本操作重复执行的次数的函数,n代表程序核心模块常见的时间复杂度,按数量级递增排列依次为:常数

01、对数阶0log

2、线形阶0n、线形对数阶XnlogT、平方阶0/、立方阶0r、指数阶02显然，时间复杂度为指数阶02“的算法效率极低,当n值稍大时，算法就失去了实际的应用价值所谓空间复杂度，即执行这个算法需要占用多少资源可以理解为占用了多少计算机存储单元类似于时间复杂度，空间复杂度表示为Sn=0fn空间复杂度计算的空间资源，是除了程序运行期间正常占用内存以外所要开销的辅助存储单元的规模此外，随着计算机硬件性能的不断提高，程序的规模越来越庞大，算法的可读性也成为了衡量算法优劣的一个重要指标。