Java Reference
In-Depth Information
huge, occupying entire rooms.) Even so, efficiency remains an issue—in some circumstances, a
critical issue.
This chapter will introduce you to the terminology and ways that computer scientists use to
measure the efficiency of an algorithm. With this background, not only will you have an intuitive
feel for efficiency, but you also will be able to talk about efficiency in a quantitative way.
4.1
Example.
Perhaps you think that you are not likely to write a program in the near future whose
execution time is noticeably long. You might be right, but we are about to show you some simple
Java code that does take a long time to perform its computations.
Consider the problem of computing the sum 1
+
2
+
. . .
+
n
for any positive integer
n
. Figure 4-1
contains pseudocode showing three ways to solve this problem. Algorithm A computes the sum 0
+
1
+
2
+
. . .
+
n
from left to right. Algorithm B computes 0
+
(1)
+
(1
+
1)
+
(1
+
1
+
1)
+
. . .
+
(1
+
1
+
. . .
+
1).
Finally, Algorithm C uses an algebraic identity to compute the sum.
FIGURE 4-1
Three algorithms for computing the sum 1
+
2
+
. . .
+
n
for an
integer
n
>
0
Algorithm A
Algorithm B
Algorithm C
sum = 0
sum = 0
sum = n * (n + 1) / 2
for
i = 1
to
n
for
i = 1
to
n
sum = sum + i {
for
j = 1
to
i
sum = sum + 1
}
4.2
Let's translate these algorithms into Java code. If we use
long
integers, we could write the
following statements:
// Computing the sum of the consecutive integers from 1 to n:
long
n = 10000;
// ten thousand
// Algorithm A
long
sum = 0;
for
(
long
i = 1; i <= n; i++)
sum = sum + i;
System.out.println(sum);
// Algorithm B
sum =
0
;
for
(
long
i =
1
; i <= n; i++)
{
for
(
long
j =
1
; j <= i; j++)
sum = sum +
1
;
}
// end for
System.out.println(sum);
// Algorithm C
sum = n * (n +
1
) /
2
;
System.out.println(sum);
