分治算法 东南大学计算机学院方效林
东南大学计算机学院 方效林 分治算法
本章内容 分治算法的原理 n大整数乘法 矩阵乘法 求第k小元素问题 ■寻找最近点对 快速傅立叶变换 n寻找凸包
本章内容 ◼ 分治算法的原理 ◼ 大整数乘法 ◼ 矩阵乘法 ◼ 求第k小元素问题 ◼ 寻找最近点对 ◼ 快速傅立叶变换 ◼ 寻找凸包 2
分治犷法的原理 设计过程 g Divide:整个问题划分为多个子问题 a Conquer:求解各子问题(递归调用子问题的算法) g Combine:合并子问题的解,形成原始问题的解
分治算法的原理 ◼ 设计过程 Divide：整个问题划分为多个子问题 Conquer：求解各子问题(递归调用子问题的算法) Combine：合并子问题的解, 形成原始问题的解 3
分治犷法的原理 n分析过程 口建立递归方程 T(nFaT(n/b+D(n+c(n) Divide时间复杂度:D(n) 口 Conque时间复杂度:aT(n/b) n Combine: C(n) 当n<c,T(n)=(1) 递归方程求解
分治算法的原理 ◼ 分析过程 建立递归方程 ➢ T(n)= aT(n/b)+D(n)+C(n) Divide时间复杂度：D(n) Conquer时间复杂度：aT(n/b) Combine：C(n) ➢ 当n<c, T(n)=(1) 递归方程求解 4
分治犷法的原理 例1:归并排序 21254925*16083141 0816212525*314149 21254925 16083141 212525*49 08163141 2125492516083141 2125254908163141 25492516083141 212514925;161083141 T(n)=27()+0(n o(n logn)
分治算法的原理 ◼ 例1：归并排序 5 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 08 16 21 25 25* 31 41 49 21 25 25* 49 08 16 31 41 21 25 25* 49 08 16 31 41 𝑻 𝒏 = 𝟐𝑻 𝒏 𝟐 + 𝚶 𝒏 = 𝚶 𝒏 log𝒏
分治犷法的原理 例2:找最大值 21254925*16083141 41 2125492516083141 2125492516083141 T(n)=2T(x)+1 n 6
分治算法的原理 ◼ 例2：找最大值 6 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 𝑻 𝒏 = 𝟐𝑻 𝒏 𝟐 + 𝟏 = 𝒏 − 𝟏 25 49 16 41 49 41 49
折半搜索 搜索40 012345 有序顺序表 003040 5060 o low=0, high=n-1, mid=(low+high)/2 x先和md元素比较 id high 40>30 若相等,搜索成功,返回下标 23 45 若x更小,继续在前半部分搜索10203ol4o|soso n high=mid-1, mid=(low+high)/2 若x更大,继续在后半部分搜索 low mid high 40<50 o low=mid+1, mid=(low+high)/2 012345 102030405060 low mid high 搜索成功 40=40
折半搜索 ◼ 有序顺序表 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 ➢ 若相等，搜索成功，返回下标 ➢ 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 ➢ 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 7 搜索40 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 40>30 40<50 40=40 搜索成功
折半搜索 搜索25 012345 有序顺序表 003040 5060 o low=0, high=n-1, mid=(low+high)/2 x先和md元素比较 d high 25≤30 若相等,搜索成功,返回下标 23 45 若x更小,继续在前半部分搜索10203ol4o|soso n high=mid-1, mid=(low+high)/2 若x更大,继续在后半部分搜索 low mid high 25>10 o low=mid+1, mid=(low+high)/2 012345 012345 [10|20k3o4dl5 5060 102030405060 mid high low low mid high 25>20 low high,搜索失败
折半搜索 ◼ 有序顺序表 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 ➢ 若相等，搜索成功，返回下标 ➢ 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 ➢ 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 8 搜索25 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 2510 25>20 mid high low 10 20 30 40 50 60 0 1 2 3 4 5 low>high，搜索失败
折半搜索 有序顺序表 口折半搜索构造的判定树 >设满二叉树n=2h-1 则有2=n+1,h=logn+1) >平均搜索长度 ASL ICC (1*2”+2*21+3*22+…+(h-1)*2-2+h*21 n 错位相减法 (h-1)×2+1) n log2(n+1)-1slog2(n+1)-1
折半搜索 ◼ 有序顺序表 折半搜索构造的判定树 ➢ 设满二叉树n=2h-1 ➢ 则有2 h=n+1，h=log2 (n+1) ➢ 平均搜索长度 9 50 = = = = = = 30 > > > > > 20 40 60 10 log ( 1) 1 log ( 1) 1 1 (( 1) 2 1) 1 (1 * 2 2 * 2 3 * 2 ( 1) * 2 * 2 ) 1 2 2 0 1 2 2 1 + − + − + = = − + = + + + + − + − n n n n h n h h n ASL h h hsucc 错位相减法
大蓬数乘法 n位二进制整数X和Y相乘 口通常算法时间复杂性性为0(n 分治算法时间复杂度可降至0(n59) 10
大整数乘法 ◼ n位二进制整数X和Y相乘 通常算法时间复杂性性为 𝚶(𝒏 𝟐 ) 分治算法时间复杂度可降至 𝚶(𝒏 𝟏.𝟓𝟗) 10