算法设计与分析(第二章).ppt

* 计算机算法设计与分析 * 递推递归的算法复杂性 若递归元用减法递减，则为递推递归。 递减步长b对复杂性影响很小。其复杂性只取决于子任务个数a和合并开销函数D(n) 。 递推算法复杂性一般为f(n) = O(anD(n))。 因为an已经是指数函数了。故一般都认为递推算法复杂性为O(an)。 对于复杂的递推递归式，该常数a可以解相应递归式求得，它是该递归式的特征方程的根的组合。 显然合并开销函数D(n)会增大递推算法复杂性。 * 计算机算法设计与分析 * 降低递归算法复杂性 降低递归算法复杂性的方法有： 1、降低子任务的数量a； 2、降低合并开销函数D(n)。 降低合并开销函数D(n)的方法通常有： ⑴把所有递归中不变的运算都提到递归之外进行； ⑵尽可能降低递归中的运算的强度。 * 计算机算法设计与分析 * 通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系： Legal(n) = a + b + Legal(n – 2) a + c + Legal(n – 2) b + Legal(n – 1) c + Legal(n – 1) 这是个两步递归！可是我们只考虑了n = 1这一种最简单情况！ 要增加n = 0的情况。 * 计算机算法设计与分析 * 通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系： Legal(n) = a + b + Legal(n – 2) a + c + Legal(n – 2) b + Legal(n – 1) c + Legal(n – 1) 我们令当n = 0时的合法单词为空串? ，即 Legal(0) = ?。 * 计算机算法设计与分析 * 通信信道上允许传输的单词 综合n 为 0和1的最简单情况后，有： Legal(n) = ? n = 0 b n = 1 c n = 1 a n = 1 a + b + Legal(n – 2) n 1 a + c + Legal(n – 2) n 1 b + Legal(n – 1) n 1 c + Legal(n – 1) n 1 * 计算机算法设计与分析 * 程序设计的思考 现在就让我们来设计这个程序吧！ 这个程序要打印出所有在通信信道上传输的长度为n的合法单词。 现在你头脑里想象的打印 过程该是什么样子的呢？ * 计算机算法设计与分析 * 程序设计的思考 现在就让我们来设计这个程序吧！ 这个程序要打印出所有在通信信道上传输的长度为n的合法单词。 我想： 这个程序应该是从左向右逐个符号地生成每一个长度为n的合法单词。 每生成一个合法单词，就把它打印出去。 * 计算机算法设计与分析 * 程序设计的思考 现在就让我们来设计这个程序吧！ 这个程序要打印出所有在通信信道上传输的长度为n的合法单词。 我想： 那么，这个程序就应该有个存放这个长度为n的合法单词的变量，就叫它w[n]吧。 干脆把这个程序叫做Legal(w, n)好了。 * 计算机算法设计与分析 * 程序设计的思考 现在就让我们来设计这个程序吧！ 这个程序要打印出所有在通信信道上传输的长度为n的合法单词。 我想： 那么，什么时候就该打印合法单词w[n]呢？ ………… 那不就是n = 0的时候吗？…… * 计算机算法设计与分析 * 程序设计的思考 现在就让我们来设计这个程序吧！ 这个程序要打印出所有在通信信道上传输的长度为n的合法单词。 aha! I got it! 按照递归规则，从n开始，就是从左至右，将合法的符号放进w；每放一个符号，n就减一。当n个符号全都放进去了，就是n = 0了，就把w打印出去。 * 计算机算法设计与分析 * 打印合法单词的程序 Legal(w[n], int k) { if (k=0) {print w} else if (k=1) {Legal(w+a, k–1); Legal(w+b, k–1); Legal(w+c, k–1)} else {Legal(w+a+b, k–2); Legal(w+a+c, k–2); Legal(w+b, k–1); Legal(w + c, k–1)}} main(int n) {int w[n] = 0; Legal(w[n], n) } 考虑运算w +x