公共基础知识
第一章数据结构与算法11算法1算法：所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序．在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。算法实际上是一种抽象的解题方法，它具有动态性。作为一个算法．一般应具有以下几个基本特征。1可行性算法的可行性主要包括两个方面。一是算法中的每一个步骤必须是能实现的。一是算法执行的结果要能达到预期的目的。2确定性算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。3有穷性算法的有穷性，是指算法必须能在有限的时问内做完．即算法必须能在执行有限个步骤之后终止。算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，也失去了实用价值。4拥有足够的情报一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法并不有效。综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的．且是明确的，此顺序将在有限的次数下终止。2算法复杂度：算法的复杂度主要包括时间复杂度和空间复杂度。1算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量f
其中
是问题的规模。在同一问题规模下，如果算法执行所需的基本运算次数取决于某特定输入时，可以用以下两种方法来分析算法的工作量。平均性态分析，是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。算法的平均性态定义为：
2算法的空间复杂度一个算法的空间复杂度．一般是指执行这个算法所需要的内存空间。一个算法所r