An Introduction to the Analysis of Algorithms 2nd PDF

【实例简介】
算法分析导论(第2版)(英文版) 罗伯特·塞奇威克 (Robert Sedgewick) (作者), 菲利普·弗拉若莱 (Philippe Flajolet) (作者) 本书全面介绍了算法的数学分析中所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。本书的重点是“平均情况”或“概率性”分析，书中也论述了“最差情况”或“复杂性”分析所需的基本数学工具。 本书第1版为行业内的经典著作，本版不仅对书中图片和代码进行了更新，还补充了新章节。全书共9章，第1章是导论；第2~5章介绍数学方法；第6~9章介绍组合结构及其在
This page intentionally left blank AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS Second edition Robert sedgewick Princeton university Philippe Flajolet Ⅰ NRIA Rocquencourt A Addison-Wesley Upper Saddle river,NJ· Boston· Indianapolis· San francisco New York Toronto montreal London munich paris. madrid Capetown· Sydney· Tokyo· Singapore· Mexico city 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 the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals The authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for er rors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding intcrcsts. For morc information, plcasc contact U.S. Corporate and government sales (800382-3419 corpsalesepearsontechgroup. com For sales outside the United States, please contact International sales international@pearsoned com Visit us on the web: informit. com/aw Library of Congress Control Number: 2012955493 Copyright 2013 Pearson Education, Inc All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storagc in a rctricval systcm, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission 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 ISBN-13:978-0-321-90575-8 ISBN-10 0-321-90575-X Text printed in the United Sta cled paper at Courier in Westford, Massachusetts First printing, January 2013 FOREWORD EOPLE who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that sur round elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically. Mathematical models have been a crucial inspiration for all scientific activity, cvcn though thcy arc only approximatc idealizations of rcal-worl phenomena. Inside a computer, such models are more relevant than ever be- forc, bccausc computcr programs crcatc artificial worlds in which mathemat- ical models often apply precisely. I think that's why i got hooked on analysis of algorithms when I was a graduate student, and why the subject has been my main lifes work ever since Until recently, however, analysis of algorithms has lar reely remain preserve of graduate students and post-graduate researchers. Its concepts are not really esoteric or difficult, but they are relatively new, so it has taken awhile to sort out the best ways of learning them and using them Now, after more than 40 years of development, algorithmic analysis has matured to the point where it is ready to take its place in the standard com puter science curriculum. The appearance of this long-awaited textbook by Sedgewick and Flajolet is therefore most welcome. Its authors are not only worldwide leaders of the field, they also are masters of exposition. I am sure that every serious computer scientist will find this book rewarding in many wa D.E. Knuth This page intentionally left blank PREFACE His book is intended to be a thorough overview of the primary tech niques used in the mathematical analysis of algorithms. The material covered draws from classical mathematical topics, including discrete mathe matics, elementary real analysis, and combinatorics, as well as from classical computer science topics, including algorithms and data structures. The focus is on " average-case"or "probabilistic" analysis, though the basic mathematical tools required for“ worst-case”or“ complexity” analysis are covered as well We assume that the reader has some familiarity with basic concepts in both computer science and real analysis. In a nutshell, the reader should be able to both write programs and prove theorems. Otherwise, the book is intended to be self-contained The book is meant to be used as a textbook in an upper-level course on analysis of algorithms. It can also be used in a course in discrete mathematics for computer scientists, since it covers basic techniques in discrete mathemat- ics as well as combinatorics and basic properties of important discrete struc turcs within a familiar contcxt for computcr scicncc students. It is traditional to have somewhat broader coverage in such courses, but many instructors may find thc approach hcrc to bc a uscful way to engage students in a substantial portion of the material. The book also can be used to introduce students in mathematics and applicd mathematics to principlcs from computcr scicncc related to algorithms and data structures Despite thc large amount of litcraturc on thc mathcmatical analysis of lgorithms, basic information on methods and models in widespread use has not bccn directly acccssiblc to students and rcscarchcrs in thc ficld. This book aims to address this situation, bringing together a body of material intended to provide readers with both an appreciation for the challenges of the field and the background needed to learn the advanced tools being developed to meet these challenges. Supplemented by papers from the literatu book can serve as the basis for an introductory graduate course on the analysis of algo- rithms, or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this field Preparation. Mathematical maturity equivalent to one or two years'study at the college level is assumed. Basic courses in combinatorics and discrete mathematics may provide useful background (and may overlap with some PREFACE material in the book), as would courses in real analysis,numerical metho or elementary number theory. We draw on all of these areas, but summarize he necessary material here, with reference to standard texts for people who want more intormation Programming experience equivalent to one or two semesters' study at the college level, including elementary data structures, is assumed. We do not dwell on programming and implementation issues, but algorithms and data structures are the central object of our studies. Again, our treatment is complete in the sense that we summarize basic information, with reference to standard texts and primary sources Related books. Related texts include The Art of Computer Programming by Knuth; Algorithms, Fourth Edition, by Sedgewick and Wayne; Introduction to Agorithms by Cormen, Leiserson, Rivest, and Stein; and our own Analytic Combinatorics. This book could be considered supplementary to each of these In spirit, this book is closest to the pioneering books by Knuth. Our fo cus is on mathematical techniques of analysis, though, whereas Knuth's books are broad and encyclopedic in scope, with properties of algorithms playing a primary role and methods of analysis a secondary role. This book can serve as basic preparation for the advanced results covered and referred to in Knuths books. We also cover approaches and results in the analysis of algorithms that have been developed since publication of Knuths books We also strive to keep the focus on covering algorithms of fundamen tal importance and interest, such as those described in Sedgewicks algorithms now its fourth edition, coauthored by k. wayne That book surveys classic algorithms for sorting and searching, and for processing graphs and strings Our cmphasis is on mathematics nccdcd to support scicntific studics that can serve as the basis of predicting performance of such algorithms and for com paring diffcrcnt algorithms on the basis of performance Cormen, Leiserson, Rivest, and Steins Introduction to algorithms has emerged as the standard textbook that provides access to the research litera ture on algorithm design. The book(and related literature) focuses on design and the theory of algorithms, usually on the basis of worst-case performance bounds. In this book, we complement this approach by focusing on the anal- ysis of algorithms, especially on techniques that can be used as the basis for scientific studies(as opposed to theoretical studies). Chapter 1 is devoted entirely to developing this context PREFACE This book also lays the groundwork for our Analytic Combinatorics, a eneral treatment that places the material here in a broader perspective and develops advanced methods and models that can serve as the basis for new research, not only in the analysis of algorithms but also in combinatorics and scientific applications more broadly. A higher level of mathematical matu rity is assumed for that volume, perhaps at the senior or beginning graduate student level. Of course, careful study of this book is adequate preparation It certainly has been our goal to make it sufficiently interesting that some readers will be inspired to tackle more advanced material How to use this book. readers of this book are likely to have rather diverse backgrounds in discrete mathematics and computer science. With this in mind, it is useful to be aware of the implicit structure of the book: nine chap ters in all, an introductory chapter followed by four chapters emphasizing mathematical methods, then four chapters emphasizing combinatorial struc- tures with applications in the analysis of algorithms, as follows INTRODUCTION ONE ANALYSIS OF ALGORITHMS DISCRETE MATHEMATICAL METHODS TWO RECURRENCE RELATIONS THREE GENERATING FUNCTIONS FOUR ASYMPTOTIC APPROXIMATIONS FIVE ANALYTIC COMBINATORICS ALGORITHMS AND COMBINATORIAL STRUCTURES SIX TREES SEVEN PERMUTATIONS EIGHT STRINGS AND TRIES NINE WORDS AND MAPPINGS Chapter 1 puts the material in the book into perspective, and will ll readers understand the basic objectives of the book and the role of the re maining chapters in meeting those objectives. Chapters 2 through 4 cover 【实例截图】
【核心代码】