[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 re​moving 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