![]() ![]() ![]() If k 1: return merge(mergesort(a), mergesort(a)) else return aġ3 Time Complexity merge() takes linear time O(k + l).įunction merge(x,y and y Output: a sorted array if k = 0, return y if l = 0, return x if x p1. comparing k with the middle located value v in A. If T(n) = a(T(⎡n/b⎤) + O(nd) for some constants a > 0, b > 1, and d ≥ 0, thenġ1 Binary Search The most popular divide-and-conquer algorithm.įinding a key k from the sorted list e.g. Karatsuba-Ofman, 1962 Can multiply two n-digit integers in O(n1.585) bit. T(n) = 3T(n/2) + O(n) ⇒ O(n1.59)įunction multiply (x, y) Input: Positive binary integers x and y Output: Their product n = max(size of x, size of y) if n = 1, return xy x_l = leftmost ⌜n/2⌝ bits of x x_r = rightmost ⌜n/2⌝ bits of x y_l = leftmost ⌜n/2⌝ bits of y y_r = rightmost ⌜n/2⌝ bits of y P1 = multiply(x_l, y_l) P2 = multiply(x_r, y_r) P3 = multiply(x_l + x_r, y_l + y_r) return P1 x 2n + (P3 - P1 - P2) x 2n/2 + P2ĩ Divide-and-Conquer Integer Multiplication So, we have three multiplications at each recursive step, and each step takes O(n) additions. The structure of a divide-and-conquer algorithm follows the structure of a proof by (strong) induction. So O(n2)ħ Improvement Since We can calculate only three multiplications (xL+xR)(yL+yR), xLyL, xRyR rather than using four multiplications xLyR, xRyL, xLyL, xRyR. 1 Divide and Conquer Algorithms Divide and conquer algorithms generally have 3 steps: divide the problem into subproblems, re-cursively solve the subproblems and combine the solutions of subproblems to create the solution to the original problem. Every recursive step requires O(n) addition. Time Complexity The algorithm will run in T(n) = 4T(n/2)+O(n) 4 multiplications and each multiplication is done from half sized bit-number. Third step: compute x⋅y through the above expression using xLyL, xLyR, xRyL, xRyR obtained from the second step. Appropriately combine their answersĤ Multiplication Multiplying the two n-digit numbers x, y using divide-and-conquer algorithm First step: split each digit into two parts, which is n/2 bits long.ĥ then, x⋅y can be written, Second Step: get values of sub equations xLyL, xLyR, xRyL, xRyR recursively. Divide-and-conquer Algorithms Some of contents in this lecture slides are from textbook Sanjoy Dasgupta, Christos Papdimitriou and Umesh Vazirani, Algorithms, McGraw-Hill, 2008.Ģ Table of Contents Basic Strategy of Divide-and-conquer Multiplicationīinary Search Merge Sort Finding Median Matrix MultiplicationĪ divide-and-conquer strategy solves a problem by Break a problem into sub problems that are themselves smaller instances of the same type of problem Solve sub problems recursively. Divide-and-conquer AlgorithmsĬomputer Algorithms Chapter 2. ![]() Divide-and-conquer Algorithms"- Presentation transcript:ġ Chapter 2. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |