分治算法 东南大学计算机学院方效林
东南大学计算机学院 方效林 分治算法
本章内容 分治算法的原理 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𝒏