联立递归 ■联立递归是同时定义几个函数,它们彼此相互 调用,从而形成递归,又称间接递归。 例如 Hilbert图案,下面所示为H1,H2和H3 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 11 联立递归 ◼ 联立递归是同时定义几个函数，它们彼此相互 调用，从而形成递归，又称间接递归。 ◼ 例如Hilbert图案，下面所示为H1，H2和H3： H1 H2 H3
Hilbert图案 ■将H记为A,将H旋转90°,180°和270°后的 图形分别记为B,C和D,其中一、二级曲线 如下所示 B 2021/22 计算机算法设计与分析 12
2021/2/21 计算机算法设计与分析 12 Hilbert图案 ◼ 将Hi记为Ai，将Hi旋转90°, 180°和270°后的 图形分别记为Bi，Ci和Di，其中一、二级曲线 如下所示： A1 B1 C1 D1 A2 A1 D1 A1 B1 B2 C1 B1 B1 A1 C2 B1 C1 D1 C1 D2 A1 D1 D1 C1
Hilbert图案 ■于是可得出这些子曲线逐级间存在如下关系: h+1:D A A; B ↑B;→B;↑ i+1: B 口D 其中,箭头表示曲线移动的方向, ■于是便可写出画这些曲线的递归子程序: 2021/221 计算机算法设计与分析 13
2021/2/21 计算机算法设计与分析 13 Hilbert图案 ◼ 于是可得出这些子曲线逐级间存在如下关系： Ai+1： Di Ai Ai Bi Bi+1： Ci Bi Bi Ai Ci+1： Bi Ci Ci Di Di+1： Ai Di Di Ci 其中，箭头表示曲线移动的方向， ◼ 于是便可写出画这些曲线的递归子程序：
Hilbert图案 ■依据A1:D←A1!A→B1有画A的子程序: A(){ if (i>0(D(i-1):x=X-h; ploting(x, y) A(i-1;y=y-h; ploting(x, y) A(i-1;x=X+h; ploting(x, y) B(I-1);}} ∥° ploting(x,y)是从画笔现行坐标到坐标(x,y)画条直线 类似地可以写出画B、C和D的曲线的子程序 ■画 Hilbert曲线的程序在调用A之前还应有一些 初始化的工作,如计算h,移动画笔至起点 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 14 Hilbert图案 ◼ 依据 Ai+1：Di Ai Ai Bi 有画A的子程序： A(i) { if (i > 0) { D(i – 1); x = x – h; ploting(x, y) ; A(i – 1); y = y – h; ploting(x, y) ; A(i – 1); x = x + h; ploting(x, y) ; B(i – 1); }} //*ploting(x, y)是从画笔现行坐标到坐标(x, y)画条直线 ◼ 类似地可以写出画B、C和D的曲线的子程序。 ◼ 画Hilbert曲线的程序在调用A之前还应有一些 初始化的工作，如计算h，移动画笔至起点
画 Hilbert图案的时间复杂性 Hilbert图案A1是由A、B1、C1、和D中的四个图案 再通过三根直线连接而成的。显然绘制A、B;、C;、和 D的复杂形式一样的。于是我们有如下的递推公式 0 n=0 T(n)= 4T(n-1)+3n>0 不难推出:T(n)=12*4-3 所以,画Hber图案的时间复杂性为O(4)。 2021/221 计算机算法设计与分析 15
2021/2/21 计算机算法设计与分析 15 画Hilbert图案的时间复杂性 ◼ Hilbert图案Ai+1是由Ai、Bi、Ci、和Di中的四个图案， 再通过三根直线连接而成的。显然绘制Ai、Bi、Ci、和 Di的复杂形式一样的。于是我们有如下的递推公式： T(n) = 0 n = 0 4T(n–1) + 3 n＞0 ◼ 不难推出： T(n) = 4T(n–1) + 3 = 4(4T(n–2) + 3 ) + 3 = n–1 i=0 = 4n (4T(0) + 3) + 3 4i = 3 4i = 3(4n+1 – 1) n i=0 ◼ 不难推出： T(n) = 12*4 n – 3。 所以，画Hilbert图案的时间复杂性为O(4n )