Complexity nomenclature
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Sat Dec 5 12:48:16 PST 2015
On 12/04/2015 10:24 PM, Timon Gehr wrote:
> void foo(@(BigO.linear) int n,@(BigO.linear) int m);
>
> But UDAs for parameters are not supported.
That's actually pretty neat and easy to work around like this:
void foo(int n, int m) @(BigOParam!2(BigO.linear, BigO.linear);
In fact I went through the implementation but soon I hit a wall: what's
the _relationship_ between the two growths? It may be the sum O(m + n)
but also the product O(m * n). So the operator must be encoded as well.
Then what do we do with more complex relationships like O((m + n) log n)
etc.
Then once you get to some reasonable formula, what's the ordering on top
of these complexities? Probably difficult.
I gave up on this for the time being. Ideas welcome.
Andrei
More information about the Digitalmars-d
mailing list