On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
On 12/04/2015 01:05 AM, Tofu Ninja wrote:
Also maybe a simpler idea would just be to annotate the the operations
with there complexity with UDAs. That way things that really care about
the complexity can get it, and those who don't can ignore it. It has the
benefit of being self documenting as well.
Well look at what the cat dragged in:
http://dpaste.dzfl.pl/711aecacc450
Following up on this, I thought I'd define a little algebra for
complexities. It will be closed (no arbitrary expressions) and will
support only the usually encountered complexities.
The idea is to allow functions to compute their own complexity in terms
of complexities of their respective primitives.
Here's the algebra.
Terms:
1 = O(1)
log = O(log n)
plog = O((log n)^k)
sqrt = O(sqrt n)
lin = O(n)
linlog = O(n * log n)
linplog = O(n * (log n)^k)
poly = O(n^k)
exp = O(2^n)
Ordering:
Terms above are in increasing order.
Summation:
x + y = max(x, y)
Product:
| 1 log plog sqrt lin linlog poly exp
-------+------------------------------------------------------------
1 | 1 log plog sqrt lin linlog poly exp
log | log plog plog ? linlog ? poly exp
plog | plog plog plog ? linplog linplog poly exp
sqrt | sqrt ? ? lin poly poly poly exp
lin | lin linlog linplog poly poly poly poly exp
linlog | linlog linplog linplog poly poly poly poly exp
poly | poly poly poly poly poly poly poly exp
exp | exp exp exp exp exp exp exp exp
I've left a few question marks for the tricky cases. Ideas?
Andrei
