Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:haley:chapter5 [2014/03/12 02:06] – archermcclellanh | courses:cs211:winter2014:journals:haley:chapter5 [2014/03/12 02:35] (current) – archermcclellanh | ||
|---|---|---|---|
| Line 23: | Line 23: | ||
| * Finally, for T(n) ≤ 2T(n/2) + O(n^2) | * Finally, for T(n) ≤ 2T(n/2) + O(n^2) | ||
| * After some work (p 220, 221), we find that T(n) ≤ O(n^2). | * After some work (p 220, 221), we find that T(n) ≤ O(n^2). | ||
| + | |||
| + | ===== 5.3: Counting Inversions ===== | ||
| + | |||
| + | * In ranking systems, we want to be able to count the inversions between two different rankings of the same objects. That is, if we take one list of rankings, we want to tell how many inversions are required to get to the other one. | ||
| + | * We recursively sort the list to be counted and the n find its inversions by merging back up. | ||
| + | * We sort the lists recursively, | ||
| + | * We merge by maintaining a pointer into each list, initialized to the front. We keep count of the inversions. While neither list is empty, we add the smaller item being pointed to to the output list, and if the item in the rightmost list is smaller, we increment the number of inversions. | ||
| + | * This runs in O(nlogn) time for an n-element list. | ||
| + | |||
| + | ===== 5.4: Finding Closest Points ===== | ||
| + | |||
| + | * Consider a collection of n points in (x,y) space. We want to find the pair of points that are closest. | ||
| + | * We start by sorting those points in increasing x order. | ||
| + | * We then find the two points in the middle of the list of points and imagine a vertical line between them. | ||
| + | * We find the closest points on each side of the line | ||
| + | * We then find the closest points across the line, that is, the points closer together than the closest points on either side of the line. | ||
| + | * Let d be the minimum distance between two points on either side. | ||
| + | * Then we only have to look within d on each side of the line. | ||
| + | * We divide this into d/2 by d/2 boxes, and for each box check the next 7 closest boxes. | ||
| + | * This only takes O(nlogn) time? DANG. | ||
| + | |||
