blob: 379e9522f14e9c9ff85f56a038bf051cad5be991 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
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
|
