Python and Schools

[Jp Calderone]

On Tue, Apr 15, 2003 at 07:07:27PM +0000, Greg Brondo wrote:
> Aahz wrote:
> >In article <v9e21mhemm8c2 at corp.supernews.com>,
> >Paul Watson <pwatson at redlinec.com> wrote:
> >
> >>We need to teach students correct design priciples to build something
> >>greater than what already exists.  We will never get very far if we
> >>require everyone to start with a quark or atom.  Yes, of course we need
> >>some people who design silicon and create microcode.  They will learn
> >>the low-level details what they need to know as they need it.  Knowing
> >>great design and organization principles will enable them to make the
> >>most of it.
> >
> >
> >While there's some truth to that, try explaining why the following code
> >is a Bad Idea to someone who has no basic understanding of CS:
> >
> >    s = ''
> >    for i in range(1000000):
> >        s += str(i)
> >
> >Knowing the difference between O(N) and O(N^2) is critical to writing
> >even the simplest programs.  OTOH, I do agree with you that focusing on
> >programming as a craft is more important to being a programmer than
> >learning CS.
> 
> I understand why the code is bad (copying the string each time in
> memory as it grows).  However, I've never understood the notation's
> O(N) and O(N2)?

  Big-O is just a way to formally describe the complexity of an algorithm. 
It tends to only be applied to the most complex (and therefore most
expensive) portion, and all the lesser parts are ignored.  It is almost
always in terms of some variable, usually (but not always) one with an
obvious meaning.  N above refers to the number of times the concatenation is
performed.  So O(N) simply means the algorithm has linear complexity - that
is, the runtime cost of running this algorithm grows directly with the
number of concatenations performed.  O(N**2) would indicate quadratic
complexity - the runtime costs grow with the square of the number of
concatenations performed.

  It also occassionally makes sense to talk about the best case, the average
case, and the worst case complexity.  For example, quick-sorting an almost
sorted list can take much longer than quick-sorting one ordered such that
the partitions are always exactly at the center of each segment being
examined.  The former of these cases is the worst case and the latter is the
best case.  In practical programming, as I believe someone else has
mentioned in this thread, often only the average case is generally
considered.

  Also note that hidden things can affect the complexity of algorithms. 
With a malloc-dependant algorithm, such as string concatenation, while your
algorithm may be O(N) or O(N**2), the algorithms you depend on may increase
the overall complexity.  While you would still talk about your algorithm
having some complexity, the actual runtime performance might vary
significantly from this, and vary significantly from environment to
environment, where the hidden complexity changes due to different library
implementations.  For this reason, the practical use of Big-O notation is
fairly limited (IMHO).

  Hope this helps,

  Jp

-- 
http://catandgirl.com/view.cgi?90
-- 
 up 26 days, 15:02, 4 users, load average: 0.29, 0.10, 0.02