CSC152 2006S, Class 33: Algorithm Analysis (1)
Admin:
* Guest lecturer - Sam takes notes in this page.
* Exam distributed Friday.
* Reading: Algorithm Analysis
* EC for attending today's talk at 4:30
Overview:
* What makes a good algorithm?
* Computational complexity
* Big-O Notation
/What Makes a Good Algorithm?/
* Student Responses
* Efficient
* Effective
* General
* Whoops ... it was a trick question. Good for _what_?
* Do we care if an algorithm takes 1 millisecond or 1 microsecond if we only run it once a day?
* Observation: The amount of time writing new code is _dwarfed_ by the amount of time you spend reading old code.
* Clear may be the most important aspect for something that does not get run a lot.
* What if your time is worth a _lot_ more than the computer's time?
* Then the algorithm should also be easy to implement.
* Consistent
* Story: Roller Coaster simulator
* 1000's of objects
* Need to sort objects during each screen refresh
* 30 refreshes per second
* So, how do we measure how long an algorithm takes?
* One answer: Time how long it takes
* Trick question: How long does it take to compute 3+4 at run time?
* Answer: Java spec says "Computed at compile time"
* How long does it take to compute "a+b"?
* Very little time
* But it depends on a number of factors. On modern computers, not all variables are "in cache" (the fast memory). It may take a while to load it from the disk.
* So we abstract: x = a + b takes "one addition plus one assignment", even though both operations take different times
* Now we can compare two algorithms by the total number of additions and assignments
* Example: How do we compute x^n, where x is a double?
multiply x by itself n times
* Java code
double result = 1.0;
for (int i = 0; i < n; i++) {
result = result * x;
}
* How long does this take?
* 2*n+2 assignments
* n additions
* n multiplications
* n comparisons
* A divide-and-conquer solution
(define (pow x n)
(cond
((zero? n) 1)
((odd? n) (* x (pow x (- n 1))))
(else (let ((tmp (pow x (/ n 2)))) (* tmp tmp)))))
* How long does this take?
* Hand waving: 2*log_2(n) recursive calls, at worst
* Sam inserts:
* If we do the odd case, in the next recursive call, we choose the even case
* In the even case, we divide the exponent by two
* log_2(n) is, approximately, "the number of times you have to divide n in half until you get 1"
* Each recursive call includes a few tests, perhaps a let, and a multiplication
* So
* 2*log_2(n) multiplications
* 2*log_2(n) tests
* Perhaps log_2(n) lets
* 2*log_2(n) function calls
* Observation: Given that we don't know about the comparative cost of the different operations, why don't we treat them all the same?
* The first algorithm takes about 5*n operations
* The second algorithm takes about 7*log_2(n) operations
* Now, do we really care whether something is 5*n or 4*n or 6*n,
particularly since we've now merged different operations? No,
we really care that it's "some number" times n.
* So, the first algorithm is "some number" times n
* The second algorithm is "some number" times log_2(n)
* How much better is the second? Let's consider a chart
n | 1 | 10 | 1000 | 10^6 |
---------------------------------------------------
Constant: 1 | 1 | 1 | 1 | 1 |
Logarithmic: log_2(n) | 0 | 3.2 | 10 | 20 |
Linear: n | 1 | 10 | 1000 | 10^6 |
Quadratic: n^2 | 1 | 100 | 10^6 | 10^12 |
Cubic: n^3 | 1 | 1000 | 10^9 | 10^18 |
NlogN: nlog_2(n) | 0 | 30 | 10000 | 2x10^7 |
* For real problems, the nlogn algorithm is significantly better than an n^2 algorithm
* Problem: What if we're using different representations?
* For BigDecimal and BigInteger, addition (and multiplication) take time relative to the size of the number (the number of columns)
* Question from "the class": Why did you make the improvement to the recursive algorithm?
* Answer from the class: One recursive call is clearly better than two
* When analyzing algorithms, we often consider: worst case, best case, average case
* Binary search is
* Constant in the best case (the thing you're looking for is in the middle)
* Logarithmic in the worst case
* Logarithmic in the average case
* Bubble sort (if you know bubble sort) is
* Linear in the best case
* Quadratic in the worst case
* Quadratic in the average case
Notation: a function is O(n) if it takes times proportional to
n.
* Sam will explain more tomorrow