Geek Answers Handbook

Is there a library for programmatically manipulating Big-O complexities?

I am interested in programming languages ​​that can justify their complexity over time. To this end, it would be very useful to have some way of representing the time complexity programmatically, which would allow me to do things like:

f_time = O(n) g_time = O(n^2) h_time = O(sqrt(n)) fastest_asymptotically = min(f_time, g_time, h_time) # = h_time total_time = f_time.inside(g_time).followed_by(h_time) # = O(n^3)

I am using Python at the moment, but I am not language bound. I experimented with sympy , but I could not find what I needed out of the box.

Is there a library that provides this feature? If not, is there an easy way to do this using a symbolic math library?

EDIT : I wrote a simple library following @ Patrick87 and it seems to work. I still wonder if there are other solutions to this problem.

+4
source share
3 answers

SymPy currently only supports an extension of 0 (you can simulate other endpoints by performing a shift). It does not support expansion at infinity, which is used in algorithmic analysis.

But it would be a good base package for it, and if you implement it, we will gladly accept the patch (nb: I am the main developer of SymPy).

Remember that the whole problem is complex, especially if you have two variables or even symbolic constants. It is also difficult if you want to support oscillation functions. EDIT: If you're interested in oscillating features, this SymPy mailing list discussion contains interesting articles.

EDIT 2: And I would recommend not trying to build it yourself from scratch, without using a computer algebra system. You will eventually have to write your own computer algebra system, which is a lot of work and even more work if you want to do it right and not have it slow. There are already many existing systems, including many that can act as libraries for code to be built on top of them (for example, SymPy).

+3
source

If you work only with the “big O” note and are interested in one function growing more or less rapidly than another, asymptotically speaking ...

  • Given functions f and g
  • Calculate the limit when n goes to infinity f (n) / g (n) using a computer algebra package
  • If the limit diverges to + infinity, then f> g in the sense that g = O (f), but f! = O (g).
  • If the limit diverges by 0, then g <e.
  • If the limit converges to a finite number, then f = g (in the sense that f = O (g) and g = O (f))
  • If the limit is undefined ... it hits me!
+1
source

You actually create / find an Expression Amplifier that can deal with:

  • + (in your terms: followed_by )
  • ***** (in your terms: inside )
  • ^, log ,! (to introduce complexity)
  • variable (e.g. n , m )
  • constant number (e.g. in 2^n )

For example, as you specified f_time.inside(g_time).followed_by(h_time) , it could be an expression like:

n*(n^2)+(n^(1/2))

and you expect the handler to make its output as follows: n^3 .

So, generally speaking, you can use simplified general expressions (if you want this to be interesting, look like Mathemetica ) to get a simplified expression like n^3+n^(1/2) , and then you need an additional processor to select the term with the highest complexity from the expression and get rid of other conditions. It would be simple, just use the table to determine the order of complexity of each kind of character.

Please note that in this case the expressions are just a symbol, you should write it as something like string (for your example: f_time = "O(n)" ), and not as a function.

+1
source

More articles:


All Articles