Algorithms.md 2.3 KB
Algorithms
Introduction
If you choose the right data structure, the algorithm will be self-evident Data structure dictates which algorithms you can apply
Functions
Mathematics
Set of X to a set of Y assigns each element of X exactly one element of Y Functions don't have side effects and only depend on their input f(x) = 42 (constant) f(x) = 2x (linear) f(x) = x^2 (quadratic) f(x) = x^3 (cubic) f(x) = log2(x) (logarithmic) f(x) = 2^x (exponential) f(x) = x! (factorial)
Factorial is recursive N! = (N - 1)! * N for all N > 0
Complexity
Constant < log(n) < √n < n < n^2 < 2^n
Logarithms
The inverse of exponentiation
If Y is product of B to the power of P ( B^P ) Y = B^P, therefore P = logB(Y)
Big O notation
Express time or space complexity (asymptotic complexity). Rough approximation of number of operations needed to execute. Time relative to number of elements. Descrbines which function best describes its growth. Big O is always a function or combination of functions where n is the number of elements.
f(n) = O(g(n)) means there are positive constants: c and k 0 <= f(n) <= cg(n) for all n >= k
Constant time operations O(1)
Does not depend on number of elements Examples:
- Adding element to end of linked list
- Accessing array by index
- Accessing root of tree
- Accessing/adding element to good hash table
Logarithmic Operations O(log(n))
Not much worse than constant time Divide to conquer Base is not relevant (especially as we approach infinity), but usually 2 Examples:
- binary search sorted array
- Add/search balanced BST
Linear Operations O(n)
- Traverse a list or array
- Add N elements to vector/list/table
- Search/Insert/Remove element to arbitrary position in list/array
- Must be traversed (average => n / 2, but treat it as n)
n log(n)
Examples:
- Insert N elements in balanced BST (N times log(n))
- Merge/Heal sort
- Quick sort (worst case O(n^2))
Quadratic Operations O(n^2)
Avoid for large data sets because number of operations grows quickly
- Nested loops
- Insert into unbalanced BST
- Bubble sort
- Insertion sort
Cubic Operations O(n^3)
- Multiplication of [n x n] matrices
Exponential Operations O(2^n)
- Traveling salesman with dynamically programmed solution
Factorial Operations O(n!)
- Don't even try it