文档介绍：THOMAS H. CORMEN
CHARLES E. LEISERSON
RONALD L. RIVEST
CLIFFORD STEIN
INTRODUCTION TO
ALGORITHMS
THIRD EDITION
Introduction to Algorithms
Third Edition
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
Introduction to Algorithms
Third Edition
The MIT Press
Cambridge, Massachusetts London, England
c 2009 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means
(including photocopying, recording, or information storage and retrieval) without permission in writing from the
publisher.
For information about special quantity discounts, please email special ******@.
This book was set in Times Roman and Mathtime Pro 2 by the authors.
Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Introduction to algorithms / Thomas H. Cormen ...[etal.].—3rded.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-262-03384-8 (hardcover : alk. paper)—ISBN 978-0-262-53305-8 (pbk. : alk. paper)
1. Computer programming. 2. Computer algorithms. I. Cormen, Thomas H.
2009
—dc22
2009008593
1098765432
Contents
Preface xiii
I Foundations
Introduction 3
1 The Role of Algorithms puting 5
Algorithms 5
Algorithms as a technology 11
2 Getting Started 16
Insertion sort 16
Analyzing algorithms 23
Designing algorithms 29
3 Growth of Functions 43
Asymptotic notation 43
Standard notations mon functions 53
4 Divide-and-Conquer 65
The maximum-subarray problem 68
Strassen’s algorithm for matrix multiplication 75
The substitution method for solving recurrences 83
The recursion-tree method for solving recurrences 88
The master method for solving recurrences 93
? Proof of the master theorem 97
5 Probabilistic Analysis and Randomized Algorithms 114
The hiring pr