Name
Abstract | ||
|---|---|---|
The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1145/3341.3349 | Commun. ACM |
Keywords | Field | DocType |
probabilistic analysis,sequential search heuristics,previous analysis,amortized analysis,move element,sequential search,relative merit,heuristics probabilistically,worst-case sense,self organization | Data structure,Computer science,Amortization (business),Amortization,Theoretical computer science,Heuristics,Artificial intelligence,Probabilistic logic,Linear search | Journal |
Volume | Issue | ISSN |
28 | 4 | 0001-0782 |
Citations | PageRank | References |
77 | 38.41 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jon L. Bentley | 1 | 380 | 66.40 |
| Catherine C. McGeoch | 2 | 262 | 59.29 |