Searching
| Algorithm | search (worst) | insert (worst) | search | insert | memory(bytes) |
|---|---|---|---|---|---|
| sequential search(unordered) | N *wN |
N *wN |
N/2 *wN/2 |
N *wN |
48N |
| binary search(ordered) | lgN *c(lgN)^2 |
N *cNlgN |
lgN *c(lgN)^2 |
N/2 *cNlgN |
16N |
| BST(semi-ordered) | N *cNlgN |
N *cNlgN |
1.39lgN *c(lgN)^2 |
1.39lgN *c(lgN)^2 |
56N |
| red-black BST(balanced) | 2lgN *c(lgN)^2 |
2lgN *c(lgN)^2 |
lgN *d(lgN)^2 |
lgN *c(lgN)^2 |
64N |
| separate chaining(array of list) | <lgN | <lgN | N/(2M) | N/M | 48N + 32M |
| linear probing(parallel arrays) | clgN *cwlgN |
clgN *cwlgN |
<1.5 *w |
<2.5 *w |
32N to 128N |
| R-way trie | *w | *w | *lgN/lgR | *w | (8R+56)N to (8R+56)Nw |
| TST | *w | *w | *1.39lgN | *w | 64N to 64Nw |
In the above table, the cost is the number of keys examined after N inserts. When there is a symbol *, we are talking about a special case when the keys are all strings. For string keys, we count the cost as number of characters examined. The key strings are from an R-character alphabet with average length w.
In sorting algorithm comparison, the soft math shows that there is a duality between sorting and searching. To sort is to search the destined position in an ordered decision tree, to search is to build a sorted datastructure that is easy to search.
sequential search <--------> insertion sort (bubble sort)
Binary search <-------> merge sort
Binary search Tree <------> quick sort
Red-black BST <------> balanced quick sort with random enough items (what is quick sort's rotate operation?)
B-Tree <---------> R-way quick sort ?
Hash Tables <--------> ?
R-way Trie <------->MSD string sort
TST <-------> 3-way string quick sort
