算法导论

　　本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系，可作为独立单元学习。所有算法都用英文和伪码描述，使具备初步编程经验的人也可读懂。全书讲解通俗易懂，且不失深度和数学上的严谨性。第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。

　　ThomasdH.Cormen是达特茅斯学院计算机科学系副教授，CharlesE.Leiserson是麻省理工学院计算机科学与电气工程系教授，RonaldL.Rivest是麻省理工学院计算机科学系教授，CliffordStein是哥伦比亚大学工程与运营研究所副教授。

目录
IFoundations
Introduction3
lTheRoleofAlgorithmsinComputing5
l.lAlgorithms5
l.2Algorithmsasatechnology10
2GettingStartedI5
2.lInsertionsort15
2.2Analyzingalgorithms21
2.3Designingalgorithms27
3GrowthofFunctions41
3.lAsymptoticnotation41
3.2Standardnotationsandcommonfunctions51
4Recurrences62
4.lThesubstitutionmethod63
4.2Therecursion-treemethod67
4.3Themastermethod73
4.4Proofofthemastertheorem76
5ProbabilisticAnalysisandRandomizedAlgorithms
5.lThehiringproblem91
5.2Indicatorrandomvariables94
5.3Randomizedalgorithms99
5.4Probabi1isticanalysisandfurtherusesofindicator106
IISortingandOrderStatisticsIntroduction123
6Heapsort127
6.lHeapsI27
6.2Maintainingtheheapproperty130
6.3Buildingaheap132
6.4Theheapsortalgorithm135
6.5Priorityqueues138
7Quicksort145
7.lDescriptionofquicksort145
7.2Performanceofquicksort149
7.3Arandomizedversionofquicksort153
7.4Analysisofquicksort55
8SortinginLinearTime165
8.lLowerboundsforsorting165
8.2Countingsorti68
8.3Radixsort170
8.4Bucketsort174
9MediansandOrderStatistics183
9.1Minimumandmaximum184
9.2Selectioninexpectedlineartime185
9.3Selectioninworst-caselineartime189
IIIDataStructuresIntroduction197
10ElementaryDataStructures200
l0.lStacksandqueues200
l0.2Linkedlists204
l0.3Implementingpointersandobjects209
l0.4Representingrootedtrees214
11HashTables221
ll.lDirect-addresstables222
11.2Hashtables224
ll.3Hashfunctions229
ll.4Openaddressing237
ll.5Perfecthashing24S
l2BinarySearchTrees253
l2.lWhatisabinarysearchtree?2S3
l2.2Queryingabinarysearchtree2S6
l2.3Insertionanddeletion261
l2.4Randoinlybuiltbinarysearchtrees265
13Red-BlackThees273
l3.lPropertiesofred-blacktrees273
l3.2Rotations277
l3.3Insertion280
l3.4Deletion288
14AugmentingDataStructures302
l4.lDynamicorderstatistics302
l4.2Howtoaugmentadatastructure308
l4.3Intervaltrees311
IVAdvancedDestheandAnalysisTechniquesIntroduction321
15DynamicProgrammingJ2J
l5.lAssembly--linescheduling324
l5.2Matrix-chainmultiplication331
l5.3Elementsofdynamicprogramming339
15.4Longestcommonsubsequence350
l5.5Optimalbinarysearchtrees356
l6GreedyAlgorithms370
l6.lAnactivity-selectionproblem371
l6.2Elementsofthegreedystrategy379
l6.3Huffmancodes385
l6.4Theoreticalfoundationsforgreedymethods393
16.5Atask-schedulingproblem399
17AmortizedAnalysis405
l7.1Aggregateanalysis406
17.2Theaccountingmethod410
17.3Thepotentialmethod412
l7.4Dynamictables416
VAdvancedDataStructuresIntroduction431
18B-Trees434
18.lDefinitionofB--trees438
l8.2BasicoperationsonB-trees44j
l8.3DeletingakeyfromaB--tree449
19BinomialHeaps455
l9.lBinomialtreesandbinomialheaps457
19.2Operationsonbinomialheaps461
20FibonacciHeaps476
20.lStructureofFibonacciheaps477
20.2Mergeable-heapoperations479
20.3Decreasingakeyanddeletinganode489
20.4Boundingthemaximumdegree493
21DataStructuresforDisjointSets498
2l.lDisjoint--setoperations498
2l.2Linked-listrepresentationofdisjointsets501
2l.3Disjoint--setforests505
2l.4Analysisofunionbyrankwithpathcompression50VIGraphAlgorithmsIntroduction525
22ElementaryGraphAlgorithms527
22.lRepresentationsofgraphs527
22.2Breadth-firstsearch531
22.3Depth-firstsearch540
22.4Topologicalsort549
22.5Stronglyconnectedcomponents552
23MinimumSpanningTrees561
23.lGrowingaminimumspanningtree562
23.2Theal