On Fri, Jan 31, 2003 at 11:41:29AM -0600, Joshua Kronengold wrote:
> Abigail writes:
> >What O (log n) efficiency? Just because the animals are in a tree doesn't
> >mean you can search in logaritmic time.
>
> True.
>
> >A tree doesn't make logaritmic
> >search - not even a binary search tree where you are doing an exact query.
> >The worst case search time will be at least as much a the maximum depth
> >of a leave. And only a balanced tree will limit this depth to O (log
> >n).
>
> But it's still log(n) in the average case. Which may or may not
> affect things.
No. It certainly is *not* O (log (n)) average case. For the same reason
that if you drive uphill with 10 mph and downhill with 30 mph, your
average speed isn't not 20 mph.
> So caching the tree (ie, in my case, I have a hash of
> animal => "path" where path (which I'm just having be a string of 0's
> and 1's, because I didn't see the point of actually having it be a bit
> vector) is a representation of the item's path in the tree (ie, yes,
> no, yes is 101) may or may not make sense computationally; it reduces
> a O(n) operation O(1), but complicates other things.
I've decided not to care too much about overall complexity. Any solution
that uses Storable, Data::Dumper, YAML or another serializing method
is already using time linear in the size of your datastructure.
Abigail
|
