Now we know what we're aiming for when we analyze an algorithm: the order of the running time. We accomplish this through the following process:

- Write the algorithm down in precise English or in any programming language, such as Java.
- Determine how many steps are accomplished by each line and how many times the line is executed. The time used by the line is the product of these two expressions. We'll say more in a moment about what constitutes a step.
- The total running time for the algorithm is the sum of the time required for each line. The order of this expression is the same as the order of the most time-consuming line.

For example, let's analyze the `size()` method from our LinkedList class. The method is reproduced in Figure 7-10, with extra line breaks added to keep each line simple. The time this takes depends on the size of the list, which we'll call n.

Each line here performs only a single step. We define a step as a constant amount of work. In other words, a step cannot depend on the size of the input or data structure in question. Any of the following constitutes a single step:

- Accessing or setting a variable or field, including an element of an array.
- Addition, subtraction, multiplication, division, and other basic arithmetic operators. (Strictly speaking, the time it takes to add two numbers depends on the sizes of the numbers. Since numbers in Java, as in most other programming languages, have a limited range, there is no potential for abuse by adding thousand-digit numbers.)
- Finding the length of an array or String.

Figure 7-10. The `size()` method from our LinkedList class. The three parts of the `for` loop header have been placed on separate lines for clarity.

1 public int size() { 2 int tally = 0; 3 for (ListNode node = front; 4 node != null; 5 node = node.getNext()) { 6 tally++; 7 } 8 return tally; 9 } |

- Comparisons using
`==`,`<`, etc. - Any fixed number of single steps, such as two additions and a variable assignment.

All of the operators which are built into the Java language, such as `+` and `&&`, count as single steps. This is not necessarily true of methods in the Java library, such as those in the collections framework. In general, if a method or operation is so trivial that you cannot imagine what simpler operations might be used to construct it, it can probably be considered a single step.

It is not a problem that some steps take longer than others, since they are all in Q(1). Suppose the longest step takes 100 milliseconds and the shortest step takes 20 milliseconds. Assuming that every step takes 100 milliseconds gives us an upper bound on the total running time. Assuming that every step takes 20 milliseconds gives us a lower bound. These two running-time expressions are in the same order, so they are equivalent for our purposes.

Returning to `size()`, we see that each line performs a single step, except for lines 7 and 9, which don't do anything. How many times is each line executed?

Lines 1, 2, 3, and 8 are executed only once. The `for` loop test on line 4 is executed once each time we enter the loop, plus one more time when the test fails. Lines 5 and 6 are each executed once on each pass through the loop.

Since `tally` starts at 0 and ends up equal to n, there must be n passes through the loop. We now know how much total time is taken by each line, as summarized in Figure 7-11. Line 4 does the most work, taking total time in Q(n + 1) = Q(n). We conclude that the running time for `size()` is linear.

Alternately, let c be the time taken by a single step. The total time taken by `size()` is:

Most algorithms are analyzed in terms of n, with n being the size of some data structure. Other analyses are possible. For example, the constructor for the Deck class from Chapter 5 is shown in Figure 7-12. This is analyzed in terms of r, the number of ranks, and s, the number of suits. The running time is dominated by line 9, which takes time in Q((r + 1)s) = Q(rs).

It is not always possible to write an algorithm so that each line takes only one step each time it is run. For example, suppose we want to analyze the contructor for the GoFish class, again in terms of r and s. The constructor is reproduced in Figure 7-13. Line 5 invokes the Deck constructor, which uses more than one step. Even though it is executed only once, this turns out to be the most expensive line in the algorithm. The analysis of `shuffle()` is left as Exercise 7.10. It is not precisely true that the `add()` method invoked in lines 12 and 13 takes constant time, but this can be remedied by a simple modification (Exercise 7.11).

Figure 7-11. The `size()` method, with the time taken by each line.

1 public int size() { // 1 step, once 2 int tally = 0; // 1 step, once 3 for (ListNode node = front; // 1 step, once 4 node != null; // 1 step, n + 1 times 5 node = node.getNext()) { // 1 step, n times 6 tally++; // 1 step, n times 7 } 8 return tally; // 1 step, once 9 } |

Figure 7-12. The constructor for the Deck class can be analyzed in terms of s, the number of suits, and r, the number of ranks.

1 /** Create all 52 Cards, in order. */ 2 public Deck() { // 1 step, once 3 cards = new Card[52]; // 1 step, once 4 size = 0; // 1 step, once 5 for (int suit = Card.SPADES; // 1 step, once 6 suit <= Card.CLUBS; // 1 step, s + 1 times 7 suit++) { // 1 step, s times 8 for (int rank = Card.ACE; // 1 step, s times 9 rank <= Card.KING; // 1 step, (r + 1)s times 10 rank++) { // 1 step, rs times 11 cards[size] = new Card(rank, suit); // 1 step, rs times 12 size += 1; // 1 step, rs times 13 } 14 } 15 } |

Since we can ignore all lines except the one with the highest-order running time, it is often okay to collapse several lines together. Specifically, all three parts of a `for` loop header can be taken as a single step, which is run as many times as the loop testthat is, one more than the number of passes through the loop. An example, a method to add up the elements of a two-dimensional array (matrix), is given in Figure 7-14.

A trickier algorithm to analyze is one which adds up only the numbers for which j The dominant term in the running time of this algorithm is the number of times the inner loop (lines 79) runs. This number is not immediately obvious, because it is different in each pass through the outer loop. When `i` is 0, the inner loop runs once. When `i` is 1, the inner loop runs twice. This continues until `i` is n 1, when the inner loop runs n times. The total number of passes through the inner loop, then, is:

This can be rewritten as:

Figure 7-13. Some lines in the constructor from the GoFish class take more than one step.

1 /** Shuffle the Deck and deal seven Cards to each player. */ 2 public GoFish() { // 1 step, once 3 computerScore = 0; // 1 step, once 4 playerScore = 0; // 1 step, once 5 deck = new Deck(); // (r + 1)s steps, once 6 deck.shuffle(); // rs + 1 steps, once 7 computerHand = new GoFishHand(); // 1 step, once 8 playerHand = new GoFishHand(); // 1 step, once 9 for (int i = 0; // 1 step, once 10 i < 7; // 1 step, 8 times 11 i++) { // 1 step, 7 times 12 playerHand.add(deck.deal()); // 1 step, 7 times 13 computerHand.add(deck.deal()); // 1 step, 7 times 14 } 15 } |

Figure 7-14. This method accepts an n x n array as input and runs in Q(n2) time. Each line counts as a single step, so only the number of times each line is executed is shown.

1 /** Return the sum of the elements of matrix. */ 2 public static double sum(double[][] matrix) { // once 3 double result = 0; // once 4 for (int i = 0; i < matrix.length; i++) { // n + 1 times 5 for (int j = 0; j < matrix[i].length; j++) { // n(n + 1) times 6 result += matrix[i][j]; // n * n times 7 } 8 } 9 return result; // once 10 } |

Figure 7-15. In this method, the number of times the inner loop runs depends on the value of i.

1 /** 2 * Return sum of matrix elements on or below the diagonal. 3 */ 4 public static double sumLowerTriangle(double[][] matrix) { 5 double result = 0; 6 for (int i = 0; i < matrix.length; i++) { 7 for (int j = 0; j <= i; j++) { 8 result += matrix[i][j]; 9 } 10 } 11 return result; 12 } |

Using the theorem from Section C.3 of Appendix C, we determine that this is:

A slightly easier approach is to reason that, on each pass through the outer loop, the inner loop runs at most n times. Using the theorem from Section C.5, we have:

Because of the , this allows us to make only a O statement, not a Q(n), while a doubly nested `for` loop typically takes time in Q(n2). Figure 7-16 shows a method with a quadruply nested `for` loop.

It is very easy to find an asymptotic upper bound on the running time of `sum4d()`. The first loop, starting on line 4, runs n times. The second loop runs at most n times for each pass through the first loop, for a total in O(n2). Similarly, the third loop takes time in O(n3). The fourth loop (and hence the entire method) takes time in O(n4).

We must be careful not to overgeneralize the result about nested loops. It is safe to use only for loops of the common form

for (int i = 0; i < n; i++) { ... }

which run at most n times.

Figure 7-16. This method, which sums the elements of a four-dimensional array, contains a quadruply nested `for` loop.

1 /** Return the sum of the elements of arr. */ 2 public static double sum4d(double[][][][] arr) { // once 3 double result = 0; // once 4 for (int i = 0; i < arr.length; i++) { // O(n) times 5 for (int j = 0; j < i; j++) { // O(n2) times 6 for (int k = 0; k < j; k++) { // O(n3) times 7 for (int m = 0; m < k; m++) { // O(n4) times 8 result += arr[i][j][k][m]; // O(n4) times 9 } 10 } 11 } 12 } 13 return result; // once 14 } |

An enhanced `for` loop also runs at most n times, where n is the number of elements in the data structure being traversed.

A loop may run less than n times if it is stopped early by a return or break statement, or if it deals with more than one element on each pass.

Exercises

7.9 |
An instance of the built-in class java.lang.BigInteger represents an integer, which can be arbitrarily large. Is it safe to assume that the |

7.10 |
Analyze the running time of the |

7.11 |
Modify the Go Fish program so that the |

7.12 |
Show that the running time of |

## Best, Worst, and Average Case |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Similar book on Amazon

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net