Complexity nomenclature

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Sun Dec 6 15:21:05 PST 2015


On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>> >
>> >The next step up the expressiveness scale would be to have a
>> >sum-of-products representation.
>> >
>> >Proof of concept (disclaimer: hacked together in the middle of the
>> >night, and not tested thoroughly):
>> >
>> >http://dpaste.dzfl.pl/d1512905accd
>> >
>> >I think this general approach is probably close to the sweet spot. ...
>> >
> Brilliant! My wife has a work emergency so I've been with the kids all day,
> but here's what can be done to make this simpler.
>
> Use D parsing and eliminate the whole parsing routine. Add multiply and
> power are all defined so you only need log of bigo.
> ...

The implementation of power on BigO given does not actually work in 
general (there should have been an enforcement that makes sure there is 
only one summand). I'll think about whether and how it can be made to 
work for multiple summands.

> Define global constants K, N, and N1 through N7. K is constant complexity
> all others are free variables.
>
> Then complexities are regular D expressions e.g BigO(N^2 * log(N)).
>
> On a the phone sry typos.

I generally tend to avoid DSLs based solely on operator overloading, as 
they don't always work and hence are awkward to evolve. Here, the 
biggest current nuisance is that the variable names are not very 
descriptive. If we'll go with a log(BigO) function, we possibly want to 
make BigO closed under log without approximating iterated logarithms:

struct Term{
     Variable n;
     Fraction[] exponents; // exponents[0] is exponent of n,
                           // exponents[1] is exponent of log n,
                           // exponents[2] is exponent of log log n, ...
}

Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence 
every BigO has a well-defined logarithm.


[1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
     O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
                      = O(log(max(f,g)))
                      ⊆ O(log(f+g)).


More information about the Digitalmars-d mailing list