Just a quick note on the
O(n)
or so-called "Big-O Notation" used by computer
science folks. It's not really "math"
1 so much as it is
an approximation. You can't get an exact number out of it,
per se, and it isn't really something you can do algebra
on in a direct sense. Quoting from that link:
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n,
which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple
of g(n). More formally it means there are positive constants c and k, such that 0 <= f(n) <= cg(n) for all n >= k. The values of c and k
must be fixed for the function f and must not depend on n.
A first year computer science textbook is certainly in order
if you want to discover some of the theory behind the way
algorithms work. The classic
White Book is a
popular choice of professors and students alike. One of the
authors is Ronald L. Rivest, the "R" in RSA encryption.
It introduces you to a variety of different algorithms
used to find substrings, sort lists, and navigate networks.
Some of this is redundant considering Perl does a lot of
this for you, but understanding the theory behind it, and
the work you are making Perl do, can help you write better
code.
The other tool that would be handy is a graphing calculator
program, or even Excel, where you could familiarize yourself
with the shape of various functions such as log(n).
In computer science terms, these shapes are used to approximate
how a function will scale, or how long it will take to run
given a data-set of size n.
Here's a quick rundown on some popular types:
- O(n) - As the data doubles in size, the algorithm
takes twice as long to run.
- O(n2) - As the data doubles in size,
the algorithm takes four times as long to run.
- O(n3) - As the data doubles in size,
the algorithm takes eight times as long to run.
- O(log n) - As the data size increases, the amount
of time the algorithm takes to run increases, but increases
less and less as the size increases more and more.
- O(en) - As the data size increases,
the amount of time the algorithm takes to run increases
exponentially, becoming very long very quickly.
For example, if you had a sort function which runs in
O(n)
time, it is fairly efficient because if you try and sort 20
things, it only takes about twice as long as sorting 10.
If you had another sort function that ran in
O(n3)
time, sorting 20 things would take eight times longer.
1. Okay, so maybe adamsj is correct in saying that it
is math, but I was merely trying to suggest that it's
not, well, mathy math, which is another way of saying
that understanding O(n) is not quite as hard as, say,
learning multi-dimensional Calculus.
I would have to agree that O(n)-notation is math inasmuch
as it uses math to express, not surprisingly,
mathematically how these functions are expected
to run.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.