26 lines
782 B
Plaintext
26 lines
782 B
Plaintext
From: justin at linus.mitre.org (Justin Sheehy)
|
|
Date: 23 Apr 1999 17:40:21 -0400
|
|
Subject: Time complexity of dictionary insertions
|
|
References: <371F2125.BEC5F892@fzi.de> <7fo08u$4j2$1@nnrp1.dejanews.com> <37207005.1CC60E1B@palladion.com>
|
|
Message-ID: <glmpv4vnhh6.fsf@caffeine.mitre.org>
|
|
X-UID: 1493
|
|
|
|
Tres Seaver <tseaver at palladion.com> writes:
|
|
|
|
> > Min O(1), Max O(N), Ave O(1). If the hash function is doing a terrible job
|
|
> > (e.g. maps every key to the same hash value), make those all O(N).
|
|
>
|
|
> C++ STL junkies know this as "amortized constant time".
|
|
|
|
So does anyone who has ever studied much at all about algorithms, data
|
|
structures, and optimization.
|
|
|
|
It's not a C++ thing. It's a computer science thing.
|
|
|
|
-Justin
|
|
|
|
|
|
|
|
|
|
|