CS240 Lecture Notes - Suffix Tree, Quadtree, Binary Search Algorithm

135 views1 pages

Document Summary

Claim: sorting items by their probabilities of access in non-increasing order minimizes the cost of search. Proof idea: if not in the right order, then if we exchange two items which are in the wrong order, then the cost decreases. Move-to-front heuristic: upon a successful search, bring the element forward to the front. (used when not knowing prob ahead of time)the cost of shift is already dealt with in the search, works well in practice. Idea: take advantage of the value of the key to determine its location. Steps: - search(x) in array in index range[l,r] Compare result with key at floor(t*l + (1-t)*r) and decide the part to recurse in. Run time: o(n) worst case but if keys are random then o(loglogn) search cost. Good for large arrays the number of comparison is still o (logn) (we have at most doubled the number of comparisons compared to binary search. Insert/delete: o(1) , search o(n) ( no bs)

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions