Algorithms in a Nutshell

Performance Families | 25

AlgorithmsThe Math of

Logarithmicalgorithms are extremely efficient because they rapidly converge on a

solution. In general, these algorithms succeed because they reduce the size of the

problem by about half each time. The GUESSINGalgorithm reaches a solution

after at mostk=⎡log (n)⎤iterations, and at theithiteration (i>0), the algorithm

computes a guess that is known to be within±ε=2k–ifrom the actual hidden

number. The quantityεis considered the error, or uncertainty. After each itera-

tion of the loop,ε is cut in half.

Another example showing efficient behavior is Newton’s method for computing

the roots of equations in one variable (in other words, for what values ofxdoes

f(x) = 0?). To find whenx*sin(x)–5*x=cos(x), setf(x)=x*sin(x)–5*x–cos(x) and its

derivative f’(x)=x*cos(x)+sin(x)–5–sin(x)=x*cos(x)–5. The Newton iteration

computesxn+1=xn–f(xn)/f’(xn). Starting with a “guess” thatxis zero, this algo-

rithm quickly determines an appropriate solution ofx=–0.189302759, as shown

in Table 2-2. The binary and decimal digits enclosed in brackets, [], are the accu-

rate digits.

Discussion 2: Sublinear O(nd) Behavior for d<1

In some cases, the behavior of an algorithm is better thanlinear, yet not as effi-

cient aslogarithmic. As discussed in Chapter 9, the kd-tree in multiple dimensions

can partition a set ofnd-dimensional points efficiently. If the tree is balanced, the

search time for range queries that conform to the axes of the points is O(n1–1/d).

Discussion 3: Linear Performance

Some problems clearly seem to require more effort to solve than others. Any eight-

year-old can evaluate 7+5 to get 12. How much harder is the problem 37+45?

}

}

// At this point, only two numbers remain. We guess one, and if it is

// wrong then the other one is the target. Thus only one more turn remains.

return 1 + turns;

}

Table 2-2. Newton’s method

n xn in decimal xn in bits (binary digits)

0 0.0

1 –0.2 [1011111111001]0011001100110011001100110...

2 –[0.18]8516717588... [1011111111001000001]0000101010000110110...

3 –[0.1893]59749489... [101111111100100000111]10011110000101101...

4 –[0.189]298621848... [10111111110010000011101]011101111111011...

5 –[0.18930]3058226... [1011111111001000001110110001]0101001001...

6 –[0.1893027]36274... [1011111111001000001110110001001]0011100...

7 –[0.189302759]639... [101111111100100000111011000100101]01001...

Example 2-1. Java code to guess number in range [low,high] (continued)

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