Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/12 23:31] – created cohene | courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/13 02:12] (current) – [5.3: Counting Inversions] cohene | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ===== 5.1: A First Recurrence: The Mergesort Algorithm===== | ===== 5.1: A First Recurrence: The Mergesort Algorithm===== | ||
| + | |||
| + | The Mergesort Algorithm shows the general approach to analyzing divide-and-conquer algorithms. Mergesort can be summarized as follows: | ||
| + | " | ||
| + | |||
| + | Any algorithm that fits this pattern would spend O(n) time dividing the input into two pieces with a size of n/2. It then spends the worst-case running time, T(n/2) dividing each of those sections, finally running in O(n) time to combine the solutions. This is an example of a recurrence relation: T(n) <= 2T(n/2) + cn or as T(n)<= 2T(n/2)+ O(n). The most natural way to find a recurrence solution is to " | ||
| + | |||
| + | Unrolling Mergesort, we see that it takes at most cn plus the time in all subsequent calls. The next level therefore takes cn/2, totaling to at most cn, and so on and so on. This allows us to identify a pattern and then sum it over all levels of recursion, which if we have cn work over log n levels, it gives us a runtime of O(n log n). | ||
| + | |||
| + | We can also solve this problem using substitution or partial substitution. | ||
| Line 7: | Line 16: | ||
| ===== 5.2: Further Recurrence Relations===== | ===== 5.2: Further Recurrence Relations===== | ||
| + | Like Mergesort, there is a general class of algorithms that have recursive calls on q subproblems of size n/2 and then combine results in O(n) time. | ||
| + | For the case of q>2, however, we unroll this following the previous style. First, we analyze the first few levels, and then identify a pattern. Finally, we apply a partial substitution. | ||
| + | When q=1, the outcome is entirely different, however, we still solve the problem the same way. We can sum this up as any function with q=1 is bounded by O(n). | ||
| ===== 5.3: Counting Inversions===== | ===== 5.3: Counting Inversions===== | ||
| + | This problem occurs when trying to analyze rankings. Websites such as Facebook use this method when trying to find things one might " | ||
| + | We can count the inversions in O(n log n) time. First, we divide the list into two pieces, and count the number of inversions in each half separately. Then, we count the number of inversions between the two halves. This routine is known as Merge-and-Count. When comparing the two lists, we take the smaller one and append it to a new list. | ||
