0%
1. 1. Big Picture
- What makes a program better？many valid criteria, which are often in conflict.
- omputer scientists love
- Time
- Memory
- trade off
- sum of 1-n：
- simple add
- gauss formula
2. 2. Big O Notation
| f(n) |
Name |
| 1 |
Constant |
| $log n$ |
Logarithmic |
| $n$ |
Linear |
| $nlogn$ |
Log Linear |
| $n^2$ |
Quadratic |
| $n^3$ |
Cubic |
| $2^n$ |
Exponential |
3. 3. Example :Anagram Detection
- Checking off: check one by one ,$O(n^2)$.
- Sort and Compare: $O(nlogn)$
- Brute Force , try all possibilities: $O(n!)$
- Count and Compare: $O(n)$
- Lists
- Indexing & Assigning & Appending $O(1)$
- Poping, Shifting & Deleting, normally $O(n)$ ,beacuse has to shift changed element
- Reversing $O(n)$
- Dictionaries
- “getting” and “setting” : $O(1)$
- Iterating & Copying: $O(n)$