Algorithms in a Nutshell (2nd ed.) [Heineman, Pollice & Selkow 2015-11-25] (draft).pdf

(5769 KB) Pobierz
www.it-ebooks.info
SECOND EDITION
Algorithms in a Nutshell 2E
George T. Heineman, Gary Pollice, and
Stanley Selkow
Boston
www.it-ebooks.info
Algorithms in a Nutshell 2E, Second Edition
by George T. Heineman, Gary Pollice, and Stanley Selkow
Copyright © 2010 George Heineman, Gary Pollice and Stanley Selkow. All rights re‐
served.
Printed in the United States of America.
Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA
95472.
O’Reilly books may be purchased for educational, business, or sales promotional use.
Online editions are also available for most titles (http://safaribooksonline.com). For
more information, contact our corporate/institutional sales department: 800-998-9938
or
corporate@oreilly.com.
Editor:
Mary Treseler
Production Editor:
FIX ME!
Copyeditor:
FIX ME!
Proofreader:
FIX ME!
January -4712:
Second Edition
Indexer:
FIX ME!
Cover Designer:
Karen Montgomery
Interior Designer:
David Futato
Illustrator:
Rebecca Demarest
Revision History for the Second Edition:
2015-07-27:
Early release revision 1
See
http://oreilly.com/catalog/errata.csp?isbn=0636920032885
for release details.
Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered
trademarks of O’Reilly Media, Inc. !!FILL THIS IN!! and related trade dress are trade‐
marks of O’Reilly Media, Inc.
Many of the designations used by manufacturers and sellers to distinguish their prod‐
ucts are claimed as trademarks. Where those designations appear in this book, and
O’Reilly Media, Inc. was aware of a trademark claim, the designations have been printed
in caps or initial caps.
While every precaution has been taken in the preparation of this book, the publisher
and authors assume no responsibility for errors or omissions, or for damages resulting
from the use of the information contained herein.
ISBN: 063-6-920-03288-5
[?]
www.it-ebooks.info
Table of Contents
1. Thinking Algorithmically. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Understand the Problem
Naive Solution
Intelligent Approaches
Greedy
Divide and Conquer
Parallel
Approximation
Generalization
Summary
1
3
4
4
5
5
6
7
8
2. The Mathematics of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Size of a Problem Instance
Rate of Growth of Functions
Analysis in the Best, Average, and Worst Cases
Worst Case
Average Case
Best Case
Performance Families
Constant Behavior
Log n Behavior
Sublinear O(n
d
) Behavior for
d
< 1
Linear Performance
n log n Performance
Quadratic Performance
Less Obvious Performance Computations
Exponential Performance
Benchmark Operations
9
10
15
18
18
19
20
20
21
23
23
27
28
30
33
33
iii
www.it-ebooks.info
Lower and Upper Bounds
References
Algorithm Template Format
Name
Input/Output
Context
Solution
Analysis
Variations
Pseudocode Template Format
Empirical Evaluation Format
Floating-Point Computation
Performance
Rounding Error
Comparing Floating Point Values
Special Quantities
Example Algorithm
Name and Synopsis
Input/Output
Context
Solution
Analysis
Common Approaches
Greedy
Divide and Conquer
Dynamic Programming
References
36
36
37
38
38
38
38
38
39
39
40
40
41
41
43
44
45
45
46
46
46
49
49
49
50
51
56
57
57
58
59
60
61
61
61
63
63
3. Algorithm Building Blocks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4. Sorting Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Overview
Terminology
Representation
Comparable Elements
Stable Sorting
Criteria for Choosing a Sorting Algorithm
Transposition Sorting
Insertion Sort
Context
Solution
iv
|
Table of Contents
www.it-ebooks.info

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin