introduction to Design & Analysis of Algorithm

【实例简介】
introduction to Design & Analysis of Algorithm
Introduction to The design Analysis of Algorithms 3 RD EDITION Vice President and editorial director ecs Marcia horton Editor-in-Chief Michael hirsch Acquisitions editor Matt Goldstein Editorial assistant Chelsea bell Vice President, Marketing Patrice Jones Marketing Manager Yezan Alayan Senior marketing coordinator Kathryn ferranti Marketing assistant Emma snider Vice president production vince o'brien Managing Editor Jeff Holcomb Production Project Manager Kayla Smith-Tarbox Senior Operations Supervisor Alan Fischer Manufacturing buyer Lisa McDowell Art Director Anthony gemmellaro Text Designer Sandra rigney Cover Designer Anthony Gemmellaro Cover Illustration Jennifer Kohnke Media editor daniel sandin Full-Service Project Management Windfall Software Composition Windfall Software, using ZzTEX Printer/Binder Courier westford Cover Printer Courier Westford Text font Times ten Copyright o 2012, 2007, 2003 Pearson Education, Inc, publishing as Addison-Wesley. All rights reserved. Printed in the United States of America. This publication is protected by Copyright and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical photocopying, recording, or likewise. To obtain permission(s)to use material from this work, please submit a written request to Pearson Education, Inc, Permissions Department, One lake Street, Upper Saddle river, New Jersey 07458, or you may fax your request to 201-236-3290 This is the e Book of the printed book and may not include any media, Website access codes or print supplements that may come packaged with the bound book Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps Library of Congress Cataloging-in-Publication Data Levitin, anan Introduction to the design analysis of algorithms / Anany Levitin -3rd ed Includes bibliographical references and index ISBN-13:978-0-13-231681-1 ISBN-10:0-13-231681-1 1. Computer algorithms. I. Title. II. Title: Introduction to the design and analysis c algorith QA76.9A43L482012 005.1—dc23 2011027089 1514131211CRW-10987654321 ISBN10:0-13-231681-1 PEARSON ISBN13:978-0-13-231681-1 Introduction to The Design Analysis of Algorithms 3RD EDITION Anany Levitin Villanova university PEARSON Boston Columbus Indianapolis New York San Francisco Uppcr Saddle River edam Cape lown IJubai I ondon Madrid Milan Munich Paris Montreal toronto Delhi Mexico City Sio Paulo Sydney Hong Kong Seoul Singapore 'Taipei Tokyo This page intentionally left blank Brief Contents he Third edi Preface XIX 2 Fundamentals of the Analysis of Algorithm Effici 3 Brute Force and Exhaustive Search 4 Decrease-and-Conquer 13 5 Divide-and-Conquer 169 6 Transf 201 253 8 Dynamic Programming 283 9 Gree 315 1 Limitations of Algorithm Pc 12 Coping with the Limitations of Algorithm Power Useful Formulas for the Analysis of Algorithms PPENDIX B Short tutorial on recurrence relations References Hints to exercis 503 Index This page intentionally left blank Contents New to the third edition Preface mic Problem Solving 9 Understanding the Problem Ascertaining the Capabilities of the Computational Device act and Approximate Problem Sol rithm and Data st Methods of specify Algorithm 3 Important Problem type 13 20 21 i 1.4 Fundamental Data Structures Linear data structures Graphs Sets and dictionaries 2 Fundamentals of the Analysis of Algorithm 1 The Analysis Me Units for Measuring Running Time Orders of growth iorst-Case, Best-Case, and Average-Case Efficiencies Recapitulation of the Analysis framework 2.2 Asymptotic Notations and Basic Efficiency Classes 52 Informal Introduction O-notation 22-notation ful Property Involving the Asymptotic nota ing Ord Exercises 2.2 2.3 Mathematical Analysis of Nonrecursive algorithms 2. 4 Mathematical Analysis of Recursive Algorithms 2.5 Example: Computing the nth Fibonacci Number 2.6 Empirical Analysis of Algorithms 2.6 2.7 Algorithm Visualization 【实例截图】
【核心代码】