which is better, string concatentation or substitution?
Ted
tedlandis at gmail.com
Mon May 8 17:44:33 CEST 2006
Thank you Roy.
It seems if you lurk here long enough you eventually get all you
questions answered without even asking!
;-)
Roy Smith wrote:
> John Salerno <johnjsal at NOSPAMgmail.com> wrote:
> >Roy Smith wrote:
> >
> >> One may be marginally faster, but they both require copying the source
> >> string, and are thus both O(n).
> >
> >Sorry, I'm not familiar with the O(n) notation.
>
> OK, here's a quick tutorial to "big-oh" notation. It's a way of
> measuring algorithmic complexity. The O stands for "on the Order
> of".
>
> For any algorithm, if you process n things (in the case of the strings
> we're talking about, n would be the total number of characters in all
> the strings), you can compute the number of steps it takes to complete
> all the processing as some function of n.
>
> For example, let's say a given algorithm took 4n^2 + 5n + 17 steps to
> complete. It doesn't take much experimentation to prove to yourself
> that for all but the very smallest values of n, the constant 17 is
> completely insignificant. In fact, n doesn't have to get very big
> before the 5n term becomes insignificant too. To a reasonable
> approximation, you could say that the algorithm takes 4n^2 steps and
> be close enough. For small values of n, this will be a bad
> approximation, but it doesn't really matter for small values of n.
> For large values of n (think hundreds, thousands or even millions),
> it's just fine.
>
> So, the first rule of O() notation is that when looking at how fast an
> algorithm runs, you need only consider the highest order term
> (i.e. the one with the biggest exponent).
>
> But, it gets even better. Let's compare two algorithms, the one
> above, which takes (approximately) 4n^2 steps, and another one which
> takes 10n steps, for varous values of n:
>
> n 10n 4n^2
> --- ------ ------
> 1 10 4
> 2 20 16
> 3 30 36
> 4 40 64
> 5 50 100
> 6 60 144
> 7 70 196
> 8 80 256
> 9 90 324
> 10 100 400
> 11 110 484
> 12 120 576
> 13 130 676
> 14 140 784
> 15 150 900
> 16 160 1024
> 17 170 1156
> 18 180 1296
> 19 190 1444
> 20 200 1600
>
> Notice that it doesn't take long for the fact that n^2 grows a lot
> faster than n to swamp the fact that 10 is bigger than 4. So the next
> step in simplification is to say that not only don't the lower-order
> terms matter, but the coefficient on the highest order term doesn't
> even matter. For a large enough n, all that matters is the exponent
> (for the moment, I'm making a further simplification that all
> algorithms can be described by polynomials with integer exponents).
>
> So, we get things like:
>
> O(n^0), which is almost always written as O(1). This is a "constant
> time" algorithm, one which takes the same amount of steps to execute
> no matter how big the input is. For example, in python, you can
> write, "x = 'foo'". That assignment statement takes the same amount
> of time no matter how long the string is. All of these execute in the
> same number of steps:
>
> x = ''
> x = 'foo'
> x = 'a very long string with lots and lots of characters'
>
> We can say that "assignment is constant time", or "assignment is
> O(1)".
>
> The next step up is O(n). This is "linear time" algorithm. It takes
> a number of steps which is directly proportional to the size of the
> input. A good example might be "if 'x' in 'bar'". The obvious way to
> implement this (and, I assume, the way it is implemented in Python),
> is to loop over the string, comparing 'x' to each character in 'bar',
> one by one. This takes as many steps as there are characters in the
> string.
>
> Next comes O(n^2), also knows as "quadratic time". This means if your
> input is of size n, the algorithm will take n^2 steps to run.
> Quadratic algorithms are generally considered very slow, and to be
> avoided if at all possible.
>
> Once you get used to thinking like this, it's easy to look at a piece
> of code and say, "oh, that's quadratic", or "that's linear", and
> instantly know which is faster for some some large input. And once
> you've started thinking like that, you've made one of the big jumps
> from thinking like a coder to thinking like a computer scientist (or,
> if you prefer, like a software engineer).
>
> Google "algorithmic complexity" or "big o notation" (perhaps spelled
> "big oh") for more info. I would normally recommend Wikipedia, but I
> just took a quick look at their "Big O notation" article, and noticed
> it's full of formal mathematical gobbledygook which just serves to
> obscure what is really a fairly easy concept.
More information about the Python-list
mailing list