Koch曲线 Koch曲线K计由4个Koch曲线K构成,并且每个 K的长度是K长度的三分之 120° 构成方法是: 画第一个K; n=1 旋转60° 0 60 0 画第二个K; 60 n=2 旋转-120°:; K K 画第三个K; 旋转60° K1画第四个K。 2021/221 计算机算法设计与分析 16
2021/2/21 计算机算法设计与分析 16 Koch曲线 ◼ Koch曲线是一种分形图形，其特点是它的每一 部分都是它自身。下面是n=1和n=2的Koch曲线： n = 1： n = 2： ◼ Koch曲线Ki+1由4个Koch曲线Ki构成，并且每个 Ki的长度是Ki+1长度的三分之一。 K0 K0 K0 K0 K1 K1 K1 K1 60° –120° 构成方法是： 画第一个Ki； 旋转60° ； 画第二个Ki； 旋转–120° ； 画第三个Ki； 旋转60° ； 画第四个Ki
绘制Koch曲线的算法 Koch(L,i){/*为长度,i为级数 if(i=0)Line(L)∥0,画条长为L的线段 else Koch(l/3, 1-1) Turn(60); Koch(L/3, 1-1) Turn(120); Koch(L/3, 1-1) Turn(60): Koch(L/,1-1);3 Draw-Koch(L,O,n){/*将角度初始化为0 Turn(0);Koch(L,n),}/伴然后再画曲线。 2021/22 计算机算法设计与分析 17
2021/2/21 计算机算法设计与分析 17 绘制Koch曲线的算法 ◼ Koch(L, i) { //*L为长度，i为级数 ◼ if (i == 0) Line(L) //*i为0，画条长为L的线段 ◼ else {Koch(L/3, i – 1); ◼ Turn(60); Koch(L/3, i – 1); ◼ Turn(–120); Koch(L/3, i – 1); ◼ Turn(60); Koch(L/3, i – 1);}} ◼ Draw-Koch(L, θ, n) {//*将角度初始化为θ； ◼ Turn(θ); Koch(L, n);}//*然后再画曲线
Koch曲线的三角形 ■右边是一个 由三条Koch 曲线构成的 角形: 2021/22 计算机算法设计与分析 18
2021/2/21 计算机算法设计与分析 18 Koch曲线的三角形 ◼ 右边是一个 由三条Koch 曲线构成的 三角形：
绘制Koch曲线的时间复杂度 ■设T(n是绘制Koch曲线K所需要的时间, 则从算法可知,T(n)满足如下递归方程: O(1) k=0 T()=4r-1)+0()k>0 ■类似的,解此递归方程可得T(n)=O(4) 2021/22 计算机算法设计与分析 19
2021/2/21 计算机算法设计与分析 19 绘制Koch曲线的时间复杂度 ◼ 设T(n)是绘制Koch曲线Kn所需要的时间， 则从算法可知，T(n)满足如下递归方程： T(n) = O(1) k = 0 4T(n–1) + O(1) k＞0 ◼ 类似的，解此递归方程可得T(n) = O(4n )