algorithms_in_a_nutshell.pdf

(12173 KB) Pobierz
Algorithms
in a Nutshell
A PRACTICAL GUIDE
George T. Heineman,
Gary Pollice & Stanley Selkow
2n
d
Ed
iti
on
ALGORITHMS
IN A NUTSHELL
Second Edition
George T. Heineman,
Gary Pollice
& Stanley Selkow
Algorithms in a Nutshell
by George T. Heineman, Gary Pollice, and Stanley Selkow
Copyright © 2016 George Heineman, Gary Pollice and Stanley Selkow. All rights reserved.
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.
Editors:
Andy Oram and Mary Treseler
Production Editor:
Colleen Lobner
Copyeditor:
Christina Edwards
Proofreader:
Jasmine Kwityn
October 2008:
March 2016:
First Edition
Second Edition
Indexer:
Judy McConville
Interior Designer:
David Futato
Cover Designer:
Karen Montgomery
Illustrator:
Rebecca Demarest
Revision History for the Second Edition
2016-03-09:
First Release
See
http://oreilly.com/catalog/errata.csp?isbn=9781491948927
for release details.
Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trade‐
marks of O’Reilly Media, Inc.
Algorithms in a Nutshell,
the cover image of a hermit crab, and
related trade dress are trademarks of O’Reilly Media, Inc.
While the publisher and the authors have used good faith efforts to ensure that the informa‐
tion and instructions contained in this work are accurate, the publisher and the authors dis‐
claim all responsibility for errors or omissions, including without limitation responsibility for
damages resulting from the use of or reliance on this work. Use of the information and
instructions contained in this work is at your own risk. If any code samples or other technol‐
ogy this work contains or describes is subject to open source licenses or the intellectual prop‐
erty rights of others, it is your responsibility to ensure that your use thereof complies with
such licenses and/or rights.
978-1-491-94892-7
[LSI]
Table of Contents
Preface to the Second Edition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1. Thinking in Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Understand the Problem
Naïve Solution
Intelligent Approaches
Summary
References
1
3
3
8
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
Performance Families
Benchmark Operations
References
Algorithm Template Format
Pseudocode Template Format
Empirical Evaluation Format
Floating-Point Computation
Example Algorithm
Common Approaches
References
Transposition Sorting
9
10
14
18
31
33
35
36
37
38
42
46
52
57
iii
3. Algorithm Building Blocks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4. Sorting Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin