Java Reference
In-Depth Information
for (each index j) {
update max, if elements i and j differ by more than max.
}
}
The following code implements the range method as described:
// returns the range of numbers in the given array
public static int range(int[] numbers) {
int maxDiff = 0;
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length; j++) {
int diff = Math.abs(numbers[j] - numbers[i]);
maxDiff = Math.max(maxDiff, diff);
}
}
return maxDiff;
}
Since the code has two nested for loops, each of which processes the entire array,
we can hypothesize that the algorithm executes roughly N 2 statements, or some mul-
tiple thereof.
We can measure the speed of this range algorithm in milliseconds by calling
range on various arrays and measuring the time elapsed. We measure the time by
acquiring the current time before and after calling range on a large array and sub-
tracting the start time from the end time.
As you can see in Figure 13.2, as the input size N doubles, the runtime of the
range method approximately quadruples. This is consistent with our hypothesis. If the
algorithm takes N 2 statements to run and we increase the input size to 2 N , the new
runtime is roughly (2 N ) 2 or 4 N 2 , which is four times as long as the original runtime.
Our code isn't very efficient for a large array. It requires over 12 seconds to exam-
ine 32,000 integers on a modern computer. In real-world data-processing situations
1000
2000
4000
8000
16000
32000
64000
Runtime (ms)
15
47
203
781
3110
12563
49937
N
60000
50000
40000
30000
20000
10000
0
Input size (N)
Figure 13.2
Runtimes for first version of range algorithm
 
Search WWH ::




Custom Search