hash and __eq__
Arnaud Delobelle
arnodel at googlemail.com
Sun May 31 07:08:33 EDT 2009
Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
> On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:
>
>> AFAIK, 'complexity' means 'worst case complexity' unless otherwise
>> stated.
>
> No, it means "average or typical case" unless otherwise specified.
> Consult almost any comp sci text book and you'll see hash tables with
> chaining (like Python dicts) described as O(1) rather than O(N),
> Quicksort as O(N log N) instead of O(N**2), and similar. If the default
> was "worst case unless otherwise specified", then Quicksort would be
> called "Slower than Bubblesort Sort".
>
> (Both are O(N**2), but Quicksort does more work.)
OK. I remember from my student years when studying complexity theory
that complexity implicitely referred to worst case complexity. I
assumed this was a widely used convention - I don't have any evidence
that it is so you may very well be correct.
Anyway, it's good to know that quicksort is O(n^2) in the worst case -
and that this worst case can crop up very easily in some situations,
especially if not too much care has been taken implementing it.
[...]
> It is simply misleading to describe dicts as O(N) without the
> qualification "if the data is chosen maliciously, or otherwise by an
> incredible fluke". And even if it isn't, Piet explicitly said he was
> talking about the average behaviour, not worst.
But the OP only mentioned 'complexity', not 'average complexity', and I
imagine that he knows the average case complexity of accessing a key in
a hashtable.
--
Arnaud
More information about the Python-list
mailing list