Algorithms in a Nutshell

Principle: Add Storage to Increase Performance | 317

Epilogue

Principle: Add Storage to Increase Performance

Many of the computations carried out by the algorithms are optimized by storing

information that reflects the results of past computations. PRIM’SALGORITHM

for computing the minimum spanning tree for a graph uses a priority queue to

store the unvisited vertices in order of their shortest distance to an initial vertexs.

During a key step in the algorithm, one must determine whether a given vertex

has already been visited. Because the binary heap implementation of the priority

queue fails to provide this operation, a separate Boolean arrayinQueueis main-

tained to record the status of each vertex. In the same algorithm, a duplicatekey

array stores the computed distances to avoid having to search again through the

priority queue. This extra storage on the order of O(n) is required to ensure the

efficient implementation of the algorithm. In most situations, as long as the over-

head is O(n), you are going to be safe.

Sometimes an entire computation can be cached to ensure that it never needs

to be recomputed. In Chapter 6, we discussed how the hash function for the

java.lang.String class stores the computed hash value to speed up its

performance.

Sometimes the nature of the input set demands a large amount of storage, such as

the dense graphs described in Chapter 6. By using a two-dimensional matrix to

store the edge information—rather than using simple adjacency lists—certain

algorithms exhibit reasonable performance. Also, you may note that for undi-

rected graphs, the algorithms are made simpler if we assume that we use twice as

much storage as necessary and store in the two-dimensional matrix information

foredgeInfo[i][j]as well asedgeInfo[j][i]. Now it would be possible to elimi-

nate this extra information if one always queried foredgeInfo[i][j]usingi≤j, but

this would further complicate each and every algorithm that simply desired to

know whether edge (i,j) exists.

Table 11-3. Chapter 6: Graph algorithms

Algorithm Best Average Worst Concepts Page

DEPTH-FIRSTSEARCH V+EV+EV+E Graph, Array, Recursion,

Backtracking

144

BREADTH-FIRSTSEARCH V+EV+EV+E Graph, Array, Queue 150

DIJKSTRA’SALGORITHMPQ (V+E)

logV

(V+E)

logV

(V+E)

logV

Weighted Directed Graph,

Array, Priority Queue, Over-

flow

154

DIJKSTRA’SALGORITHMDG V^2 +EV^2 +EV^2 +E Weighted Directed Graph,

Array, Overflow

158

BELLMAN-FORDALGORITHM V*EV*EV*E Weighted Directed Graph,

Array, Overflow

162

FLOYD-WARSHALLALGORITHM V^3 V^3 V^3 Dynamic Programming, 2D

Array, Weighted Directed

Graph, Overflow

166

PRIM’SALGORITHM (V+E)

logV

(V+E)

logV

(V+E)

logV

Weighed Graph, Binary Heap,

Priority Queue, Greedy, Array

171

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use