diff options
Diffstat (limited to '04-10.md')
| -rw-r--r-- | 04-10.md | 176 |
1 files changed, 176 insertions, 0 deletions
diff --git a/04-10.md b/04-10.md new file mode 100644 index 0000000..379e952 --- /dev/null +++ b/04-10.md @@ -0,0 +1,176 @@ +[\<- 04/08](04-08.md) + +--- + +## Review - Data Structure + +What is a data structure? +- How data is organized in memory (or hard disk) + +Why do we care about data structure? +- Efficiency - time/space efficiency +- How to measure time efficiency? + - Count # of operations + - What types of operations do we care about? + - Insertion + - Deletion + - Access/Search + - Min/Max + - Union/Merge + - When do we care? + - We only care about the one with the highest impact on efficiency + +## Review - Big-O Notation + +The correct form of big-O +- Drop all but the fastest-growing term +- Drop the constant coefficient of the remaining term +- e.g `1500n^2 + 4n + 3log(n) + 2` -> `1500n^2` -> `n^2` + - Big-O notation for this example would be O(n^2) + +How to evaluate the big-O for a piece of code? +- We mainly care about repetitive operations + - Operations that are only executed once (or constant times) will be ignored +- Loops + - Single layer loop + - Nested loop + +## Summary: Big-O for Nested Loops + +Step 1: Analyze if it's a dependent loop or independent loop. Assume the counter variable of the outsider loop is `i` +1. if `i` is not involved in insider loop -> **independent loop** +2. Otherwise -> **dependent loop** + +Step 2: If independent loop: +- O_overall = O(outsider loop) * O(insider loop) +- Otherwise (dependent loop): + - For each iteration of the outsider loop -> count # of operations for the insider loop, add them together + +## Nested Loop II - Dependent Loops + +``` +for(i=0; i<n; i=i+2){ + for(j=i; j<n; j++){ + x++; + } +} +``` + +This is a dependent loop + +|Iteration|Outsider Loop|Inner Loop Count| +|---------|-------------|----------------| +|1 |i=0 |n | +|2 |i=2 |n-2 | +|3 |i=4 |n-4 | +|n/2 |i=n-1 |1 | + +To determine the total number of iterations (let's call it x), add the values from the third column +- `x = n + (n-2) + (n-4) +...+ 1` +- Rewrite it as `x = 1 + 3 + 5 +...+ (n-2) + n` +- Rewrite again as `2x = (n+1) * (n/2)` + - `x = ((n+1)*n)/4` +- Big-O notation simplified: O(x) = O(n^2) + +## More Big-O Examples + +``` +for(i=0; i<n; i=i+n){ + x++; +} +``` + +- Only 4 steps of iteration + - O(1) (easy level) + +``` +for(i=1; i<n; i=i*3){ + x++; +} +``` + +- Figute out how many steps of iteration: + - iteration 1: i=1 (3^0) + - iteration 2: i=3 (3^1) + - iteration 3: i=9 (3^2) + - iteration 4: i=27 (3^3) + - iteration x: i=n (3^(x-1)) + +- 3^(x-1) = n -> x = log3(n)+1 + - O(x) = O(log(n)) + +``` +for(i=0; i<n; i=i+3){ + f(); //f() is O(n^2) +} +``` + +- (n/3) iterations * O(n^2) = O(n^3) + +``` +for(i=0; i<n; i++){ + g(); //g() is O(log(n)) +} + +for(j=0; j<n; j++){ + x++; +} +``` + +- The first loop has n iterations + - O(n) * O(log(n)) = O(nlog(n)) +- The second loop has n iterations + - O(n) * O(1) = O(n) +- The total big-O is O(nlog(n)) + O(n) = O(nlog(n)) + - O(n) is a lower term, so disregard + +``` +for(i=n; i>=1; i=i/3){ + for(j=0; j<n; j++){ + x++; + } +} +``` + +- Notice: independent loops +- Outer loop: O(log(n)) +- Inner loop: O(n) +- x++: O(1) (this step is sometimes ignored) +- O(log(n)) * O(n) * O(1) = O(nlog(n)) + +``` +for(i=1; i<=n; i=i*2){ + for(j=1; j<=n; j=j+i){ + x++; + } +} +``` + +- Notice: Dependent Loop + +|Iteration|Outsider Loop|Inner Loop Count| +|---------|-------------|----------------| +|1 |i=1 |n | +|2 |i=2 |n/2 | +|3 |i=4 |n/4 | +|4 |i=8 |n/8 | +|n |i=n |1 | + +- Now we need to sum each row of the inner loop count column (call it x) + - `x = n + (n/2) + (n/4) +...+ 1` + - O(x) = `n[1+(1/2)+(1/4)+...+(1/n)]` + - Eventually, O(n) (!) (that's pretty good) + +## Common Big-O Complexity Classes + +The following is listed from most to least efficient +- Constant O(1) +- Logarithmic O(log(n)) +- Linear O(n) +- Log-Linear O(n) +- Quadratic O(n^2) +- Cubic O(n^3) +- Polynomial O(n^k) +- Exponential O(2^n) or O(k^n) +- Factorial O(n!) +- Anything worse than Exponential (actually, even quadratic) are considered pretty bad |