20-Apr-2013 02:12, Ivan Kazmenko пишет:
With n = 30_000 as in the example, this takes time of the order of a
second on a modern computer, which is clearly O(n^2). I am using DMD
2.062.
Optimization flags if any?
Both "-O" and no-flags give quadratic behavior.
I sought after
-O -inline -release
In non-release mode it tests that it's sorted on exit etc.
Anyway it's 8x times as fast with -release -inline for me but the
progression is similarly bad.
Well, if that does not convince you the time grows faster than n-log-n,
maybe this comparison shall (dmd -O, Core i7-2600K @3400 MHz):
n T, seconds
15_000 0.312
30_000 1.076
60_000 3.775
120_000 11.247
With n growing x2, the time grows x3 to x4 at each step.
--
Dmitry Olshansky
