Java Reference
In-Depth Information
efficient.” In this sense, all of the factors mentioned above should cancel out of the
comparison because they apply to both algorithms equally.
If you truly wish to understand the running time of an algorithm, there are other
factors that are more appropriate to consider than machine speed, programming
language, compiler, and so forth. Ideally we would measure the running time of
the algorithm under standard benchmark conditions. However, we have no way
to calculate the running time reliably other than to run an implementation of the
algorithm on some computer. The only alternative is to use some other measure as
a surrogate for running time.
Of primary consideration when estimating an algorithm's performance is the
number of basic operations required by the algorithm to process an input of a
certain size. The terms “basic operations” and “size” are both rather vague and
depend on the algorithm being analyzed. Size is often the number of inputs pro-
cessed. For example, when comparing sorting algorithms, the size of the problem
is typically measured by the number of records to be sorted. A basic operation
must have the property that its time to complete does not depend on the particular
values of its operands. Adding or comparing two integer variables are examples
of basic operations in most programming languages. Summing the contents of an
array containing n integers is not, because the cost depends on the value of n (i.e.,
the size of the input).
Example3.1
Consider a simple algorithm to solve the problem of finding
the largest value in an array of n integers. The algorithm looks at each
integer in turn, saving the position of the largest value seen so far. This
algorithm is called the largest-value sequential search and is illustrated by
the following function:
/
**
@returnPositionoflargestvalueinarrayA
*
/
staticintlargest(int[]A){
intcurrlarge=0;//Holdslargestelementposition
for(inti=1;i<A.length;i++) //Foreachelement
if(A[currlarge]<A[i]) //ifA[i]islarger
currlarge=i; // rememberitsposition
returncurrlarge; //Returnlargestposition
}
Here, the size of the problem is
A.length
, the number of integers stored
in array
A
. The basic operation is to compare an integer's value to that of
the largest value seen so far. It is reasonable to assume that it takes a fixed
amount of time to do one such comparison, regardless of the value of the
two integers or their positions in the array.
Because the most important factor affecting running time is normally
size of the input, for a given input size n we often express the time T to run
