第1天:全部的基本概念Poi
t1:算法的基本概念5考点精讲1、算法:是指解题方案的准确而完整的描述。(1)算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述,但程序通常还要考虑程序运行时的环境限制等。(2)算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。2、算法的基本特征:(1)可行性,例如101211012的问题(2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性;例在特殊情况时,数学公式是正确的,但计算机就是无法操作。(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义。例如13的无理数问题。(4)拥有足够的情报。所有的各种可能情况都要考虑到。3、一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。(1)算法的时间复杂度是指执行算法所需要的计算工作量,可以执行算法的过程中所需要的基本运算的执行次数来度量。分析算法工作量的方法有:平均性态分析、最坏情况分析。(2)算法的空间复杂度是指执行这个算法所需要的内存空间。主要包括:算法程序所占的空间;输入的初始数据所占的空间;算法执行过程中所需要的额外空间。真题分析【真题1】算法的有穷性是指________。(2008年4月)A)算法程序的长度是有限的B)算法只能被有限的用户使用C)算法程序的运行时间是有限的
fD)算法程序所处理的数据量是有限的解析:算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。答案:C【真题2】问题处理方案的正确而完整的描述称为__【5】__。(2005年4月)解析:算法是问题处理方案正确而完整的描述。答案:算法【真题3】算法的空间复杂度是指________。(2009年9月)A)算法程序中的语句或指令条数B)算法在执行过程中所需要的临时工作单元数C)算法在执行过程中所需要的计算机内部存储空间D)算法所处理的数据量6解析:算法的空间复杂度是指执行这个算法所需要的计算机内部存储空间(简称内存空间)。答案:C
【真题4】下列叙述中正确的是________。(2007年3月)A)数据的逻辑结构与存储结构是一一对应的B)算法的时间复杂度与空间复杂度一定相关C)算法的效率只与问题的规模有关,而与数据r