算法设计与分析

阶乘

Public static int factorial (int n){ If (n==0) return 1; return*factorial(n-1); } Hanoi

Public static void hanoi(int n, int a, int b, int c){ if (n>0){

hanoi（n-1,a,b,c）; move(a,b);

hanoi(n-1,c,b,a); }}

Fibonacci 数列

Public static int Fibonacci(int n){ If (n<=1) return 1;

Return Fibonacci(n-1)+Fibonacci(n-2); }

算法：算法是指解决问题的方法的过程。满足一下性质：1输入：有零个或多个输入；2输出：产生知道一个量作为输出；3确定性：组成算法的每条指令时清晰的、无歧义的。4、有限性：每天指令执行的次数和时间都是有限的。

程序：程序是算法用某种程序设计语言具体实现的，它不满足算法的有限性。 P类：有确定性多项式时间算法

P={L|L是一个能在多项式时间内被一台DTM所接受的语言} N类：没有确定性多项式时间算法

NP类：有非确定性多项式时间算法，但不能证明没有确定性多项式时间算法 NP={L|L是一个能再多项式时间内能被一台NDTM所接受的语言} NPC问题：定义：语言L是NP完全的当且仅当 (1)L∈NP；(2)对于所有L’∈NP有L’ ∝p L。

如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。 NP完全问题 P是否等于NP

NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略：

(1)只对问题的特殊实例求解

(2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解

(5)用启发式方法求解 算法的复杂性（度）：算法运行所需要的计算机资源量。需要的时间资源量成为时间复杂性，需要的控件资源量成为控件复杂性。 贪心算法满足的性质：（1）贪心选择性质；（2）最优子结构性质。 动态规划的两个重要性质：（1）最优子结构；（2）问题重叠性质； 递归：直接或间接地调用自身的算法成为递归算法：

动态规划算法基本思想是将待求解问题分解成若干个子问题，先求解子问题，

然后从这些子问题的解得到原问题的解。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 （碰壁回头）

分支限界法基本思想常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。常见的分支限界法 （1）队列式(FIFO)分支限界法

按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n！的各算法，若用ABC公司的计算机在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答： n'=100n;

n'2=100n2，? n'=10n;

n'3=100n3，? n'=102/3n=4.64n;

n'!=100n!，? n'