算法4_递推关系：分而治之.pptx

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Multiplying binary numbers: Use Gauss’ trick! Now what is the recurrence relation? Running time? ;Given an input array of real numbers, we want to output the array in sorted order MergeSort idea: Split the array in half Sort each half Merge the two halves together ;;How do we merge?;What is the running time of this function?;What is the running time of MergeSort?;CircularShift problem Suppose you are given a sorted array S with no duplicate values that has been circularly shifted. For example: You don’t know how many positions it has been shifted by. Describe a log(n) algorithm to find the maximum value ;;Find the non-duplicate Given a sorted array S of integers. Each value present appears exactly twice in S, except for one (so if there are k distinct values, the length is 2k – 1). Find the non-duplicate value in better than O(logn) time. ;;The standard algorithm: What is the running time?;A more efficient method was discovered by Volker Strassen in 1969! What is the running time of this divide-and-conquer strategy? ;But it turns out that there is a way to decompose the problem into 7 subproblems, not 8! What is the running time?;MaxSubarraySum problem Given an array S with real numbers (some may be negative), find indices i, j with i j such that the sum of values S[i], …, S[j] is maximized Hint: how can you combine results from subarrays? ;;How do we find the median of an array? Sort the array; pick the midpoint What is the running time of this? But sorting does a lot of extra work… can we do better?;Let’s define a more general problem: given an array S, find the kth smallest value of the array A divide-and-conquer solution to the above problem: Pick a value v from the array S Split S into three arrays: SL, Sv, and SR SL contains values smaller than v Sv contains values equal to v SR contains values greater than v ;Example: For a given v, what is the time required to perform this split?;From this split, how do we decide which arr