分治法的复杂性分析 个分治法将规模为η的问題分成k个规模为n/m的子问題去解。设分解阀 值n0=1,且 adhoc解规模为1的问題耗费1个单位肘间。再设将原问题分解为 k个子问題以及用 merge将k个子问题的解合并为原问题的解需用f(n)个单位 时间。用T()表示该分治法解规模为|P|=n的问题所需的计算时间,则有: T(n IET(n/m)+f(n)n> 通过迭代法求得方程的解:7(m)=nm4+∑k/(m/m) J 注意:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足 够平滑,那么由η等于m的方幂时T(η)的值可以估计T(η)的增长速度。通常假定 T(n)是单调上升的,从而当m≤n<m+时,T(m)sT(m)<T(m+1)
17 分治法的复杂性分析 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀 值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为 k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位 时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有： 1 1 ( / ) ( ) (1) ( ) = + = n n kT n m f n O T n 通过迭代法求得方程的解： − = = + log 1 0 log ( ) ( / ) n m j j j k T n n m k f n m 注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足 够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定 T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi )≤T(n)<T(mi+1)
分治法例子 Examples: ● Merge sort o Binary search Powering a number ● Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problem(多数问题) ●循环赛日程表
18 Examples: ⚫ Merge sort ⚫ Binary Search ⚫ Powering a number ⚫ Fibonacci number ⚫ Multiplication of two matrices ⚫ VLSI layout ⚫ Multiplication of two numbers ⚫ Finding Minimum and Maximum ⚫ Majority problem (多数问题) ⚫ 循环赛日程表 分治法例子
Binary Search(二分查找) 1.问题:在已排序的数组中找到指定的元素x
19 1. 问题：在已排序的数组中找到指定的元素x。 Binary Search(二分查找)
Binary Search 1.问题:在已排序的数组中找到指定的元素x。 2.分治法: Divide:将x与数组的中间元素比较大小 Conquer:递归地在一个数组中查找x Combine: trivia,不用合并
20 1. 问题：在已排序的数组中找到指定的元素x。 2. 分治法： • Divide ：将x与数组的中间元素比较大小 • Conquer：递归地在一个数组中查找x • Combine ：trivial，不用合并。 Binary Search
Binary Search 问题:在已排序的数组中找到指定的元素x 2.分治法: Divide:将x与数组的中间元素比较大小 Conquer:递归地在一个数组中查找x Combine: trivia,不用合并。 3.运行时间: T(n)=T(n/2)+(1) o(gn) 21
21 1. 问题：在已排序的数组中找到指定的元素x。 2. 分治法： • Divide ：将x与数组的中间元素比较大小 • Conquer：递归地在一个数组中查找x • Combine ：trivial，不用合并。 3. 运行时间： T(n)=T(n/2)+Θ(1) = Θ(lgn) Binary Search