generating points on a grid - efficiently
Josiah Carlson
jcarlson at nospam.uci.edu
Mon Mar 8 23:03:43 EST 2004
> Firstly, the code runs in exponential time. Is there any way to
> rewrite it to make it more efficient? It seems that this could be
> formulated as a recursive problem but I can't seem to get at it.
The code does not run in exponential time. It runs in linear time to
the number of grid points that exist. Depending on your input, this can
vary.
For example, let us say that I have two axes, X, Y (where X and Y are
lists of grid points). An optimal algorithm to generate all possible
pairs will take len(X)*len(Y) time.
For three axes, X, Y, Z, it will take len(X)*len(Y)*len(Z) time.
In general, for k axes and lists of points all of length n, it will take
O(n^k) time.
That is polynomial, not exponential.
- Josiah
More information about the Python-list
mailing list