Timon Gehr <[email protected]> wrote: > On 12/04/2015 07:37 PM, Andrei Alexandrescu wrote: >> Following up on this, I thought I'd define a little algebra .... >> It will be closed (no arbitrary expressions) >> ... > > I think that the exponents matter. E.g. n^1.5 vs n^2. > The algebra can be made more expressive while simplifying its > implementation. > >> >> 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) > > Example alternative: > > struct BigO{ > Fraction logExp; > Fraction polyExp; > Fraction expBase; > > bool opCmp(BigO rhs){ > return > tuple(expBase,polyExp,logExp).opCmp(tuple(rhs.expBase,polyExp,logExp)); > } > BigO opBinary(string op:"*")(BigO rhs){ > return > BigO(logExp+rhs.logExp,polyExp+rhs.polyExp,expBase*rhs.expBase); > } > // ... > } > > Your cases then become: > > O(1): expBase=1, polyExp=0, logExp=0; > O(log n): expBase=1, polyExp=0, logExp=1; > O((log n)^k): expBase=1, polyExp=0, logExp=k; > O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0; > O(n): expBase=1, polyExp=1, logExp=0; > O(n * log n): expBase=1, polyExp=1, logExp=1; > O(n * (log n)^k): expBase=1, polyExp=1, logExp=k; > O(n^k): expBase=1, polyExp=k, logExp=0; > O(2^n): expBase=2, polyExp=0, logExp=0; > > Combinations just work, especially n^(1/2) * log n. > > >
Nice, I'll continue with this. Thanks! I won't use expBase because no operation leads to it; instead I'll just lump everything superpoly into one "fast growing" category.
