3 ms·
You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec18.html http://www.cs.cornell.edu/courses/cs312/2006sp/lect
by btilly 12y ago
You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec18.html http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec1... on the topic:
Amortized analysis refers to determining the time-averaged running time for a sequence of operations.
Note that you are averaging over a sequence of operations, and not any combination of inputs. As that article goes on to explain, amortized analysis is the right thing to use for figuring out the total running time of a sequence of operations.
Let's be concrete. In the case of a dynamically resized hash, the bound on an individual hash insertion when the hashing function works is O(n) because you could be looking at the unlucky insertion that resized the hash. The amortized cost is O(1) because you get to spread that expensive resize over many individual operations. If you're building a hard real time system, you should focus on the O(n) and not use that data structure. If you just want to build a hash table, the O(1) is what matters.
What about the amortized cost of many random hash lookups with linked-list conflict resolution? The distribution of buckets with different numbers of items approximately follows a Poisson distribution. From that we can estimate the average number of comparisons. And find out that the amortized cost is on average O(1).