[OpenSCAD] Programming in Functional OpenSCAD
NateTG
nate-openscadforum at pedantic.org
Wed Jan 31 09:30:05 EST 2018
> Under my initial hyphotesis that copies are made, an insertion or deletion
from a 2-3 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2).
Those are both totally plausible to me. I may have misunderstood this:
> For instance, the element insertion and removing from 2-3 trees have
> order O(log n). However, an analysis of your implementation in OpenSCAD
> will show that its order of complexity is O(n2) or worst due to the
> repeated structure copies required by any change in it.
Where I thought the claim was that a single insertion was O(N^2).
> I got worst than linear time building trees by insertion of 2500-30000
> elements.
Building a tree from N elements is expected to take O(N log N) time - which
is worse than linear.
> To minimize stack overflows I have used the tail recursive versions:
> ...
> BTW, your insertion code does not deal well with some sequences having
> repeated values.
Thanks for that info. I still don't really understand the "this tail
recurses" thing.
--
Sent from: http://forum.openscad.org/
More information about the Discuss
mailing list