Complexity nomenclature
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Fri Dec 4 12:03:16 PST 2015
Timon Gehr <timon.gehr at gmx.ch> 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.
More information about the Digitalmars-d
mailing list