|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
> It wasn't clever; it was vanity. I didn't want anyone else to see how
> crappy my algorithm was.
Psst. You could've taken it as a compliment and let the rest of us
wonder.
> If the ancestor lists have sizes M and N, that takes O(MN) time.
True, but in a reasonable tree with T nodes, M and N are log T.
> It seems to me that it should be possible to do it faster.
> [...]
>
>> Either way, I don't think you're looking at much less than 15-20 "lines".
>> You could apply some obfuscation to make it take less vertical space, but
>> you're not likely to make it much less computationally complex.
>
> I wonder what reasons you have for saying so.
It's been a long time since I had a formal data structures or analysis of
algorithms class, so I'm sorta winging it here.
With no knowledge about the structure of the tree or any ordering of nodes
in it (other than the 'parent' relationship), you have two choices: start
with the nodes you're given and work backwards until you find an ancestor,
or build a new representation of the tree where you have more information
for each node (specifically, which other sets of nodes it is youngest
common ancestor for). If your tree nodes don't have methods for accessing
their children, even rebuilding your tree must start at the input nodes.
At least you'd get the benefit of having some of the work done already on
repeated queries.
Having no knowledge of the tree is what makes it O(MN). If the nodes are
sorted, or if we can find out what level a node is at (without having to
test parent() all the way back to root), there are much better clues. The
fact that there can be multiple trees (roots A and M in your sample)
doesn't help.
Of course, there's always Quantum::Superpositions...
j
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**
|
|