Graphics Programs Reference
In-Depth Information
0x720
Algorithmic Run Time
Algorithmic run time is a bit different from the run time of a program. Since
an algorithm is simply an idea, there's no limit to the processing speed for
evaluating the algorithm. This means that an expression of algorithmic run
time in minutes or seconds is meaningless.
Without factors such as processor speed and architecture, the important
unknown for an algorithm is input size . A sorting algorithm running on 1,000
elements will certainly take longer than the same sorting algorithm running
on 10 elements. The input size is generally denoted by n , and each atomic
step can be expressed as a number. The run time of a simple algorithm, such
as the one that follows, can be expressed in terms of n .
for(i = 1 to n) {
Do something;
Do another thing;
}
D o one last thing;
This algorithm loops n times, each time doing two actions, and then
does one last action, so the time complexity for this algorithm would be 2 n + 1.
A more complex algorithm with an additional nested loop tacked on, shown
below, would have a time complexity of n 2 + 2 n + 1, since the new action is
executed n 2 times.
for(x = 1 to n) {
for(y = 1 to n) {
Do the new action;
}
}
for(i = 1 to n) {
Do something;
Do another thing;
}
Do one last thing;
But this level of detail for time complexity is still too granular. For
example, as n becomes larger, the relative difference between 2 n + 5 and
2 n + 365 becomes less and less. However, as n becomes larger, the relative
difference between 2 n 2 + 5 and 2 n + 5 becomes larger and larger. This type
of generalized trending is what is most important to the run time of an
algorithm.
Consider two algorithms, one with a time complexity of 2 n + 365 and
the other with 2 n 2 + 5. The 2 n 2 + 5 algorithm will outperform the 2 n + 365
algorithm on small values for n . But for n = 30, both algorithms perform
equally, and for all n greater than 30, the 2 n + 365 algorithm will outperform
the 2 n 2 + 5 algorithm. Since there are only 30 values for n in which the
2 n 2 + 5 algorithm performs better, but an infinite number of values for n
in which the 2 n + 365 algorithm performs better, the 2 n + 365 algorithm is
generally more efficient.
Search WWH ::




Custom Search