算法设计与分析 复习

算法设计与分析 复习 算法与程序

算法：解决问题的方法或过程，是满足下述性质的指令序列。

输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。

确定性：组成算法的每条指令清晰、无歧义。

有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

程序：

程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。

例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

描述算法与算法设计 算法分析的基本原则 算法分析的基本原则

时间复杂度(time complexity)T(n) 时间复杂度指程序执行时所用的时间。

在使用解析方法时程序p的时间复杂度表示为输入量的函数T。 机器独立的分析方法-解析的方法.

在解析地分析时间复杂度时,使用以下两种时间单位并计算：

操作计数(operation count):算法的基本操作 (程序)步计数(step count):分析全部程序

要点:基本操作或程序步的执行时间必须是常数。 最好，最坏和平均情形时间复杂度

当长度相同的不同输入有不同的计算时间时，时间复杂度分析分别考虑三种情形：即最好，最坏和平均. 当应用对计算时间有严格要求时，应做最坏情形分析-upper bound. 最好情形分析给出一个算法的计算时间的下界，用来否定一个算法. 渐近分析,符号(О,Ω,Θ)

计算机科学使用最多的符号-讨论算法时使用的共同语言.

渐近分析-随n的增加T(n)的增长率

渐近分析(续) 大?

f(n)=?(g(n)) iff 存在常数c和n0使得对所有n>n0,有f(n)>cg(n)成立.

渐近分析(续)

称g(n)为f(n)的渐近下界 例如,

f(n)=0.001n2-10n-1000=?(n2) 因为:limf(n)/n2=0.001

渐近分析(续) 符号Θ

如果f(n)=O(g(n))同时 f(n)=?(g(n))则f(n)=Θ(g(n)),并称f(n)与g(n)同阶. Lim f(n)/g(n)=c, 0

g(n)取上述初等函数 渐近分析(续)

当f(n)为算法的时间复杂度函数时，称g(n)为该算法的复杂度的阶。 第2章 递归与分治策略 算法总体思想

将要求解的较大规模的问题分割成k个更小规模的子问题。 2.1 递归的概念

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

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 2.1 递归的概念 例1 阶乘函数

阶乘函数可递归地定义为：

2.1 递归的概念 例2 Fibonacci数列

无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： 2.1 递归的概念 例4 排列问题

设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列 非递归算法：字典序法

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。 2.1 递归的概念 例5 整数划分问题

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。

例如正整数6有如下11种不同的划分： 6； 5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。

递归小结

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

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 递归小结

解决方法：在递归算法中消除递归调用，使其转化为非递归算法。

1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2.用递推来实现递归函数。

3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 分治法的适用条件

分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解；

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。 分治法的基本步骤

divide-and-conquer(P) {

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

divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++)

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

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

人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 二分搜索技术

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 分析：

? 该问题的规模缩小到一定的程度就可以容易地解决； ? 该问题可以分解为若干个规模较小的相同问题; ? 分解出的子问题的解可以合并为原问题的解； ? 分解出的各个子问题是相互独立的。

分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法：

public static int binarySearch(int [] a, int x, int n) {

// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x // 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left <= right) {

int middle = (left + right)/2;

if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; }

return -1; // 未找到x }

算法复杂度分析：

每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。 棋盘覆盖

合并排序

第3章 动态规划

本文来源：https://www.bwwdw.com/article/9dwd.html