算法设计与分析复习

分治法求全排列。

算法描述。分治法求解问题分为三个步骤：

分解：将问题分为若干个子问题。

解决：递归地求解每个子问题。

合并：将每个子问题的解合并成为整个问题的解。

现在我们需要求具有n个元素的数组a的全排列。例如：大小为3的数组a=[a,b,c] (为方便起见，我把引号全都省略了，其实应该是a=['a','b','c']。

下同），它的全排列为：

[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]

这是一个大小为 n!*n 的二维数组。

使用分治算法求解全排列的过程如下。

分解：将数组分为子数组 a[1..k-1] 和一个元素 a[k]。 1≤k≤n)

解决：递归地求解每个子数组 a[1..k-1] 的全排列，直至子数组a[1..k-1]为空时结束递归。

合并：将上一步的结果—a[1..k-1]的全排列（一个二维数组）与元素a[k]合并，得出a[1..k]的全排列。例如：

]与 a 合并得到 [[a]]

[[a]] 与 b 合并得到 [[a,b], b,a]]

[[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]

#include

using namespace std;

#define n 4

char str[10];

void perm(char *str, int k, int m);

void swap(char &a, char &b);

int main()

perm(str, 1, n);

return 0;

void perm(char *str, int k, int m)

void swap(char &a, char &b)

分治法求第k小元素算法：

求一列数中的第k小元素，利用分治的策略进行递归求解。

首先随便指定一个数，这里我指定的是第一个数为第k小元素记为randk，将数组中其他的数与findk进行比较，比他小的放在左边，大的放在右边，如果randk左边的元素个数为k-1个，说明findk就是你所要找的元素，如果左边的元素个数》k-1，说明你要找的元素在左边的数中，继续使用相同的方法在左边的数中进行查找，如果左边的元素的个数**：

#define array_max 200

void swap(int &a,int &b)

void out(int a,int n)

if(il>=ir) break;

swap(a[il],a[ir]);

swap(a[op],a[ir]);

return ir;}

nt findk(int a,int op,int n,int k)

第2章，导引与基本数据结构：

1、什么是算法，算法的5个特性；对一个算法作出全面分析的两个阶段。

5个特性：确定性、能行性、输入、输出、有穷性。

两个阶段：事前分析、事后测试。

3、多项式时间算法：可用多项式（函数）对其计算时间限界的算法。

4、常见的多项式限界函数所表示算法时间复杂度的排序：

5、指数时间算法：计算时间用指数函数限界的算法。

6、常见的指数时间限界函数：

2n)

7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。

第章递归与分治算法。

1、理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决n阶汉诺塔问题的解，并能分析写出3阶汉诺塔问题的递归执行轨迹。

2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。

5、分治法的基本思想：是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

6、掌握二分检索算法，如给一个实例，可以模拟出low，hig，mid的运行轨迹。（74页）知道并能证明二分检索算法平均时间复杂度是( logn)

7、掌握找最大和最小元素的递归分治算法。(79页)

9、合并排序的时间复杂度是：t(n)=o(nlogn)。

第5章贪心方法。

1、贪心方法：是根据具体的问题，选取一种量度标准，按此标准对n个输入进行排序，然后按该顺序一次输入一个量。如果这个输入量和当前的部分最优解加在一起不能产生一个可行解，则不把此输入量加入到这个部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。

2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择。

3、贪心算法的基本要素：贪心选择性质和最优子结构性质。

4、掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。

第6章动态规划。

1、将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。

最优子结构性质：该问题的最优解包含着其子问题的最优解。

2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。

3、理解并掌握多段图的动态规划求解过程，包括递推步骤。

第8章回溯法。

1、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

4、回溯法效率的因素：

（1）产生x[k]的时间。

（2）满足显约束的x[k]值的个数。

（3）计算约束函数constraint的时间。

（4）计算上界函数bound的时间。

（5）满足约束函数和上界函数约束的所有x[k]的个数。

第9章分支限界法（了解）

1、分支限界法的基本思想：

1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。

算法设计与分析复习

算法设计与分析复习

算法分析与设计复习

算法设计与分析复习

其他用户还读了