tailieunhanh - Lecture Algorithm design - Chapter 5: Divide and conquer I
Lecture Algorithm design - Chapter 5: Divide and conquer I include all of the following: Mergesort, counting inversions, closest pair of points, randomized quicksort, median and selection. For more details, inviting you refer to the above lesson. | 5. Divide And Conquer I mergesort counting inversions closest pair of points randomized quicksort median and selection Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http wayne kleinberg-tardos Last updated on Oct 2 2013 9 51 AM Divide-and-conquer paradigm Divide-and-conquer. Divide up problem into several subproblems. Solve each subproblem recursively. Combine solutions to subproblems into overall solution. Most common usage. Divide problem of size n into two subproblems of size n 2 in linear time. Solve two subproblems recursively. Combine two solutions into overall solution in linear time. Consequence. Brute force n2 . Divide-and-conquer 0 n log n . attributed to Julius Caesar 2 Section 5. Divide and Conquer .
đang nạp các trang xem trước