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.
