This is a draft cheat sheet. It is a work in progress and is not finished yet.
Complexities
Name |
Worst case |
Average case |
Best case |
Fractional Knapsack |
O(n*log(n)) |
0-1 Knapsack |
O(n*W) |
MergeSort |
O(n*log(n)) |
Selection-Sort |
O(n^2) |
Insertion-sort |
O(n^2) |
Heap-sort |
O(n*log(n)) |
Quick-sort |
O(n^2) |
|
O(n*log(n)) |
ComparisonBased Sort |
|
|
Ω(n*log(n)) |
BucketSort |
O(n + N) |
RadixSort |
O(d*(n + N)) |
QuickSelect |
O(n^2) |
O(n) |
O(n) |
|
|
Divide-and-Conquer
Divide-and conquer is a
general algorithm design
paradigm:
-> Divide: divide the input data S in
two or more disjoint subsets S1,
S2, ...
-> Conquer: solve the subproblems
recursively
-> Combine: combine the solutions
for S1, S2, ..., into a solution for S |
|
|
|
