note
jryan
<p>
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:
</p>
<code>
# 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[$_]);
}
}
</code>
<p>
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:
</p>
<code>
# 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
}
}
</code>
<p>
Of course, the secret is to know where to apply these optimizations, which is often harder than it seems :)
</p>
227909
227909