|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 >
|
|
相关知识点：35个
|
|
|
|
|
|
|
算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程，并且具有下列特性：
|
|
|
|
（1）有穷性。一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
|
|
|
|
（2）确定性。算法的每一步必须是确切定义的，不能有歧义。
|
|
|
|
（3）可行性。算法应该是可行的，这意味着算法中所有要进行的运算都能够由相应的计算装置所理解和实现，并可通过有穷次运算完成。
|
|
|
|
（4）输入。一个算法有零个或多个输入，它们是算法所需的初始量或被加工的对象的表示。这些输入取自特定的对象集合。
|
|
|
|
（5）输出。一个算法有一个或多个输出，它们是与输入有特定关系的量。
|
|
|
|
因此，算法实质上是特定问题的可行的求解方法、规则和步骤。一个算法的优劣可从以下几个方面考查：
|
|
|
|
（1）正确性。正确性也称为有效性，是指算法能满足具体问题的要求。即对任何合法的输入，算法都能得到正确的结果。
|
|
|
|
（2）可读性。可读性指算法被理解的难易程度。人们常把算法的可读性放在比较重要的位置，因为晦涩难懂的算法不易交流和推广使用，也难以修改和扩展。因此，设计的算法应尽可能简单易懂。
|
|
|
|
（3）健壮性。健壮性也称为鲁棒性，即对非法输入的抵抗能力。对于非法的输入数据，算法应能加以识别和处理，而不会产生误动作或执行过程失控。
|
|
|
|
（4）效率。粗略地讲，就是算法运行时花费的时间和使用的空间。对算法的理想要求是运行时间短、占用空间小。
|
|
|
|
|
|
算法与数据结构密切相关，算法实现时总是建立在一定的数据结构基础之上。
|
|
|
|
计算机程序从根本上看包括两方面的内容：一是对数据的描述，二是对操作（运算）的描述。概括来讲，在程序中需要指定数据的类型和数据的组织形式就是定义数据结构，描述的操作步骤就构成了算法。因此，从某种意义上可以说“数据结构＋算法＝程序”。
|
|
|
|
当然，设计程序时还需选择不同的程序设计方法、程序语言及工具。但是，数据结构和算法仍然是程序中最为核心的内容。用计算机求解问题时，一般应先设计初步的数据结构，然后再考虑相关的算法及其实现。设计数据结构时应当考虑可扩展性，修改数据结构会影响算法的实现方案。
|
|
|
|
|
|
算法的描述方法有很多，若用程序语言描述，就成了计算机程序。常用的算法描述方法有流程图、N/S盒图、伪代码和决策表等。
|
|
|
|
（1）流程图。流程图（flow chart）即程序框图，是历史最久、流行最广的一种算法的图形表示方法。每个算法都可由若干张流程图描述。流程图给出了算法中所进行的操作以及这些操作执行的逻辑顺序。程序流程图包括三种基本成分：加工步骤，用方框表示；逻辑条件，用菱形表示；控制流，用箭头表示。流程图中常用的几种符号如下图所示。
|
|
|
|
|
|
|
|
例如，求正整数m和n的最大公约数流程图如下图（a）所示。
|
|
|
|
|
|
|
若流程图中的循环结构通过控制变量以确定的步长进行计次循环，则可用 和 分别表示“循环开始”和“循环结束”，并在“循环开始”框中标注“循环控制变量：初始值，终止值，增量”，如上图（b）所示。
|
|
|
|
（2）N/S盒图。盒图是结构化程序设计出现之后，为支持这种设计方法而产生的一种描述工具。N/S盒图的基本元素与控制结构如下图所示。在N/S图中，每个处理步骤用一个盒子表示，盒子可以嵌套。对于每个盒子，只能从上面进入，从下面走出，除此之外别无其他出入口，所以盒图限制了随意的控制转移，保证了程序的良好结构。
|
|
|
|
|
|
|
|
用N/S盒图描述求最大公约数的欧几里德算法，如下图所示。
|
|
|
|
|
|
|
|
（3）伪代码。用伪代码描述算法的特点是借助于程序语言的语法结构和自然语言叙述，使算法具有良好的结构又不拘泥于程序语言的限制。这样的算法易读易写，而且容易转换成程序。
|
|
|
|
（4）决策表。决策表是一种图形工具，它将比较复杂的决策问题简洁、明确、一目了然地描述出来。例如，如果订购金额超过500元，以前没有欠账，则发出批准单和提货单；如果订购金额超过500元，但以前的欠账尚未还清，则发不予批准的通知；如果订购金额低于500元，则不论以前的欠账是否还清都发批准单和提货单，在欠账未还清的情况下还要发出“催款单”。处理该问题的决策表如下表所示。
|
|
|
|
|
|
|
|
|
|
解决同一个问题总是存在多种算法，每个算法在计算机上执行时，都要消耗时间（CPU执行指令的时间）和使用存储空间资源。因此，设计算法时需要考虑算法运行时所花费的时间和使用的空间，以时间复杂度和空间复杂度表示。
|
|
|
|
由于算法往往和需要求解的问题规模相关，因此常将问题规模n作为一个参照量，求算法的时间、空间开销和n的关系。详细分析指令的执行时间会涉及计算机运行过程的细节，因此时间消耗情况难以精确表示，所以算法分析时常采用算法的时空开销随n的增长趋势来表示其时空复杂度。
|
|
|
|
对于一个算法的时间开销T（n），从数量级大小考虑，当n增大到一定值后，T（n）计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都可以忽略，即釆用渐进分析，表示为T（n）=O（f（n））。其中，n反映问题的规模，T（n）是算法运行所消耗时间或存储空间的总量，O是数学分析中常用的符号“大O”，而f（n）是自变量为n的某个具体的函数表达式。例如，若f（n）=n2+2n+1，则T（n）=O（n2）。
|
|
|
|
|
|
语句频度（frequency count）是指语句被重复执行的次数，即对于某个基本语句，若在算法的执行过程中被执行n次，则其语句频度为n。这里的“语句”是指描述算法的基本语句（基本操作），它的执行是不可分割的，因此，循环语句的整体、函数调用语句不能算作基本语句，因为它们还包括循环体或函数体。
|
|
|
|
算法中各基本语句的语句频度之和表示算法的执行时间。
|
|
|
|
例如，对于下面的三个程序段（1）、（2）、（3），其实现基本操作“x增1”的语句++x的语句频度分别为1、n、n2。
|
|
|
|
|
|
（2）for（i=1；i<=n；i++）｛s+=x；++x；｝
|
|
|
|
|
|
|
|
|
|
因此，程序段（1）、（2）、（3）的时间复杂度分别为O（1）、O（n）、O（n2），分别称为常量阶、线性阶和平方阶。若程序段（1）、（2）、（3）组成一个算法的整体，则该算法的时间复杂度为O（n2）。
|
|
|
