It should be noted that many algorithm's O time can be reduced. For instance, many O(n^2) algorithms can be reduced to O(n log(n)) by finding a way to cut the inner loop short. A famous example is bubblesort:
# O(n^2)
for my $i (0..$#a-1) {
for (0..$#a-1-$i) {
($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_])
if ($a[$_+1] < $a[$_]);
}
}
# O(n log(n))
for my $i (0..$#a-1) {
# looping over already-sorted items is not needed
for (0..$#a-1-$i) {
($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_])
if ($a[$_+1] < $a[$_]);
}
}
O(n) algorithms that involve a search via a loop can sometimes be
reduced from O(n) to O(log(n)) by breaking out of the loop once a
"result" is found:
# O(n)
my $truestatus;
foreach my $item (@list) {
$truestatus = 1 if (some_condition);
}
# O(log(n))
my $truestatus;
foreach my $item (@list) {
# if some_condition is going to be valid for at least one $item in
# @list, then the limit of the average runtime will approach
# O(log n).
if (some_condition) {
$truestatus = 1;
last
}
}
Of course, the secret is to know where to apply these optimizations, which is often harder than it seems :)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.