Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_7 [2012/03/07 03:42] – section 5.3 garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_7 [2012/03/07 04:00] (current) – fixed equation scaling garrettheath4 |
|---|
| This section of the reading describes mergesort as the most canonical divide-and-conquer algorithm. A **divide-and-conquer algorithm** is an algorithm that //divides// the input into multiple pieces (usually 2), //solves// each subproblem using recursion, and then //combines// the results of those recursive calls into a solution. As with all recursion, the recursive calls in a divide-and-conquer algorithm need to have a base case so that the algorithm has a point at which it stops dividing and starts conquering. Usually this "bottom out" point is when the recursive method is called on an input of some predefined constant size, such as 1. | This section of the reading describes mergesort as the most canonical divide-and-conquer algorithm. A **divide-and-conquer algorithm** is an algorithm that //divides// the input into multiple pieces (usually 2), //solves// each subproblem using recursion, and then //combines// the results of those recursive calls into a solution. As with all recursion, the recursive calls in a divide-and-conquer algorithm need to have a base case so that the algorithm has a point at which it stops dividing and starts conquering. Usually this "bottom out" point is when the recursive method is called on an input of some predefined constant size, such as 1. |
| |
| Divide-and-conquer algorithms are a little less straightforward in computing an algorithm's order complexity, but their efficiency can be expressed as a **recurrence relation**. Mergesort can be measured by the number of comparisons based on the input size. This measurment can be expressed as a function that computes the number of comparisons (or "time") based on the input size ''n'': | Divide-and-conquer algorithms are a little less straightforward in computing an algorithm's time complexity, but their efficiency can be expressed as a **recurrence relation**. Mergesort can be measured by the number of comparisons based on the input size. This measurment can be expressed as a function that computes the number of comparisons (or "time") based on the input size ''n'': |
| | ''T(n) ≤ 2T(n/2) + cn'' | if ''n > 2'' | | | ''T(n) ≤ 2T(n/2) + cn'' | if ''n > 2'' | |
| | ''T(2) ≤ c'' | if ''n = 2'' | | | ''T(2) ≤ c'' | if ''n = 2'' | |
| |
| == Quadratic Split and Reduce == | == Quadratic Split and Reduce == |
| {{:courses:cs211:winter2012:journals:garrett:entries:journal_7_-_equation_5-2c.png?99}} | {{:courses:cs211:winter2012:journals:garrett:entries:journal_7_-_equation_5-2c.png?100|}} |
| |
| === 5.3: Counting Inversions === | === 5.3: Counting Inversions === |
| |1|2|4|3|5| | |1|2|4|3|5| |
| ^1^2^3^4^5^ | ^1^2^3^4^5^ |
| | |
| | We can use the algorithm on __Pages 224-225__ to count inversions. This algorithm has a time complexity of: |
| | {{:courses:cs211:winter2012:journals:garrett:entries:bigo-n-log-n.png?80|}}, meaning that that is the the time it would take to find the number of inversions and perform them. |
| |
| |
| |
| ~~DISCUSSION~~ | ~~DISCUSSION~~ |
