算法知识点总结.docVIP

算法是指解决问题的一种方法或一个过程。更严格的讲，算法是若干指令的有穷序列。性质：(1)输入：有零个或者多个由外部提供的量作为算法的输入。作为算法加工对象的量值，通常体现为算法中的一组变量。(2)输出：算法产生至少一个量作为输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。(3)确定性：组成算法的每条指令是清晰、无歧义的。对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行（可行性）。并且在任何条件下，算法都只有一条执行路径。(4)有限性：算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的。

程序和算法的区别：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序，通过特定的算法来实现。该子程序得到输出结果后便终止。

算法分析是对一个算法所消耗资源进行估算。资源消耗指时间、空间的耗费。算法分析的目的就是通过对解决同一问题的多个不同算法进行时空耗费这两方面的分析.比较求解同一问题的多个不同算法的效率。

一般情况下将最坏情况下的时间耗费的极限作为算法的时间耗费，称为时间复杂性。可操作性最好最有实际价值的是最坏情况下的时间复杂性。

渐进复杂性：当n单调增加且趋于∞时，T(n)也将单调增加且趋于∞。对于T(n)，如果存在T~(n)，当n→∞时，(T(n)-T~(n))/T(n)→0，称T~(n)是T(n)当N→∞时的渐近性态，或称为算法A当N→∞的渐近复杂性。

渐进意义下的记号OΩθo：以下设f(N)和g(N)是定义在整数集上的正函数。O:如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时还说f(N)的阶不高于g(N)的阶。根据符号O的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界，这个上界的阶越低，则评估就越精细，结果就越有价值。Ω：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N),则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N)).这时还说f(N)的阶不低于g(N)的阶。根据符号Ω的定义，用它评估算法的复杂性，得到的只是该复杂性的一个下界，这个下界的阶越高，则评估就越精细，结果就越有价值。Θ：定义f(N)=θ(g(N))，当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))，这时我们说f(N)与g(N)同阶。O:如果对于任意给定的ε0,都存在正整数N0，使得当N≥N0时，有f(N)/g(N)ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g（N)）。

递归的基本要素：1初始值（边界条件），每个递归函数都必须有非递归定义的初始值。2递归定义式（递归方程）。阶乘函数可递归地定义为：n!=1n=0（边界条件，给出了这个函数的初值，是非递归定义的，这是每个函数所必须的，否则递归函数就无法计算。）和n(n-1)!n0（是递归方程）

Intfactorial(intn)

{

if(n==0)return1;

returnn*factorial(n-1);

}

直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为。

分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，递归的解这些子问题，然后将各子问题的解合并得到原问题的解。它的一般的算法设计模式如下：

divide-and-conquer(P)

{

if(|P|=n0)adhoc(P);//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for(i=1,i=k,i++)

yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}

其中|P|表示问题P的规