第三单元 分治法.pptVIP

Divide-and-conquer（分治法） Divide - and – Conquer分治法 Sentinel监视哨 在数组、线性表、序列的一端插入1个在数组（或序列）中不出现的特殊数字、字符，从而减少控制变量的比较次数，达到提高效率的目的。这个特殊数字（字符）称为监视哨 Mathematical induction. Powerful and general proof technique in discrete mathematics To prove a theorem true for all integers k≥0: Base case: prove it to be true for n = 0; Induction hypothesis: assuming it is true for arbitrary n Induction step: show it is true for n+1 Claim: 0 + 1+ 2+3 + … + n = n(n + 1)/2 for all n≥0 Proof: (by mathematical induction) Base case (n=0) 0 = 0(0+1)/2 Induction hypothesis: assume 0 + 1 + 2 + … + n = n(n+1) / 2 Induction step: 0 + 1 + 2 + … + n + n + 1 = n(n+1) / 2 + n + 1 = (n+1)(n+2)/2 思考题 Page 36 2.3-1 2.3-7 * * （一种算法设计技术） To solve P: -- Divide P into smaller problems P1, P2, …, Pk原问题分解成一序列子问题 -- Conquer by solving the (smaller) subproblems recursively递归地解决各子问题，若子问题规模足够小，直接求解 -- Combine the solutions to P1, P2, …, Pk into the solution for P子问题的结果合并成原问题的解 Problem(size n) Combine sub problem 1 sub problem 2 sub problem k … sub problem 11 sub problem 12 sub problem 1k … sub problem 21 sub problem 22 sub problem 1k … … ……………………… sub problem 1’ sub problem 2’ sub problem 3’ ……………… ……………… directly solvable Divide - and - Conquer Recursive in structure Problem(size n) sub problem 1 sub problem 2 sub problem k … sub problem 21 sub problem 22 sub problem 2k … ?:Divide ?:solve recursively ?:Combine Divide - and - Conquer Problem(size n) sub problem 1 sub problem 2 sub problem k … sub problem 21 sub problem 22 sub problem 2k … ?:Divide ?:solve recursively ?:Combine Divide - and - Conquer Problem(size n) sub problem 1 sub problem 2 sub problem k … sub problem 21 sub problem 22 sub problem 2k … ?:Divide ?:solve recursively ?:Combine Divide - and - Conquer Using divide-and-conquer, we can obtain a merge-sort algorithm -- Divide: Divide the n el