算法技术手册

出版时间：2009-4  出版社：东南大学出版社  作者：海涅曼 (Heineman.G.T.) 等 著  页数：343  
Tag标签：无  

内容概要

　　创造稳定的软件需要有效的算法，但是程序设计者们很少能在问题出现之前就想到。《算法技术手册（影印版）》描述了现有的可以解决多种问题的算法，并且能够帮助你根据需求选择并实现正确的算法——只需要一定的数学知识即可理解并分析算法执行。相对于理论来说，本书更注重实际运用，书中提供了多种程序语言中可用的有效代码解决方案，可轻而易举地适合一个特定的项目。有了这本书，你可以：　　解决特定编码问题或改进现有解决方案的执行；　　迅速确定与需要解决的问题相关的算法，并判定为什么这样的算法是正确的；　　探索C、C++、Java、Ruby中的算法解决方案，伴有实现诀窍；　　了解一个算法预期的执行情况及最佳的执行条件；　　发现不同算法中相似设计产生的冲突；　　学习先进的数据结构以改进算法效率。　　有了《算法技术手册》，你可以学习如何改进算法的性能，这是软件应用成功的关键。

作者简介

　　George T.Heineman，Gary Pollice和Stanley Selkow均为 Woree ste r PolYteChniC In stitute（伍斯特理工学院）计算机科学系的教授。George是《Component—B ased Software Engineering：Putting the Pieces Together》（Addison—Wesley（的合编者，Gary则是《Head First Object-Oriented Analysis and Design》（OReilly）的合著者。

书籍目录

Part 11. Algorithms MatterUnderstand the ProblemExperiment if NecessaryAlgorithms to the RescueSide StoryThe Moral of the StoryReferences2. The Mathematics of AlgorithmsSize of a Problem InstanceRate of Growth of FunctionsAnalysis in the Best, Average, and Worst Cases.Performance FamiliesMix of OperationsBenchmark OperatxonsOne Final PointReferences3. Patterns and DomainsPatterns: A Communication LanguageAlgorithm Pattern FormatPseudocode Pattern FormatDesign FormatEmpirical Evaluation FormatDomains and AlgorithmsFloating-Point ComputationsManual Memory AllocationChoosing a Programming LanguageReferencesPart 24. Sorting AlgorithmsOverviewInsertion SortMedian SortQuicksortSelection SortHeap SortCounting SortBucket SortCriteria for Choosing a Sorting AlgorithmReferences5. SearchingOverviewSequential SearchBinary SearchHash-based SearchBinary Tree Search6. GraphAIgorithmsOverviewDepth-First SearchBreadth-First SearchSingle-Source Shortest PathAll Pairs Shortest PathMinimum Spanning Tree AlgorithmsReferences7. Path Finding in AIOverviewDepth-First SearchBreadth-First SearchASearchComparisonMinimaxNegMaxAlphaBetaReferences8. Network Flow AlgorithmsOverviewMaximum FlowBipartite MatchingReflections on Augmenting PathsMinimum Cost FlowTransshipmentTransportationAssignmentLinear ProgrammingReferences9. Computational GeometryOverviewConvex Hull ScanLineSweepNearest Neighbor QueriesRange QueriesReferencesPart 310. When All Else FailsVariations on a ThemeApproximation AlgorithmsOffline AlgorithmsParallel AlgorithmsRandomized AlgorithmsAlgorithms That Can Be Wrong, but with Diminishing Probability References11. EpilogueOverviewPrinciple: Know Your DataPrinciple: Decompose the Problem into Smaller ProblemsPrinciple: Choose the Right Data StructurePrinciple: Add Storage to Increase PerformancePrinciple: If No Solution Is Evident, Construct a SearchPrinciple: If No Solution Is Evident, Reduce Your Problem toAnother Problem That Has a SolutionPrinciple: Writing Algorithms Is Hard——Testing Algorithms Is HarderPart 4Appendix: BenchmarkingIndex

章节摘录

　　In the sortPointers function of Example 4－11.each element in the input iSinserted into itS associated bucket based upon the provided hash function；thistakes linear，or o（n），time.The elements in the buckets are not sorted，butbecause of the careful design of the hash function.we know that all elements inbucket bj are smaller than the elements in bucket bj，ifi〈LAs the values are extracted from the buckets and written back into the input array.INSERTION SORT iS used when a bucket contains more than a single element.ForBUCKET SORT tO exhibit O（n）behavior.we must guarantee that the total time tOsort each of these buckets iS also O（n）.Let’S define　tO be the number ofelements partitioned in bucket bi.We can treat ni as a random variable（usingstatistical theory）.NOW consider the expected value　Each element inthe input set has probability p=1／n of being inserted into a given bucket becauseeach of these elements iS uniformly drawn from the range[0，1）.Therefore，E[ni）：n*p=n*（1／n）=1.From this equation we can compute the expected value ofni2.This is criticalbecause it is the factor that determines the COSt of INSERTION SORT，which runsin a worst case of O（n2）.We compute E[ni2]=（1-1／n）+1=（2-1In），which showsthat E[n‘’]is a constant.This means that when we sum up the COSTS of executingINSERTION SORT on all n buckets，the expected performance COSt remains.

媒体关注与评论

　　“作者汲取了大量鲜为人知的文献资料，这本不可或缺的指南巩固了理论与实际操作的完美平衡。通过它来理解算法变得更加轻松容易。”　　——Matthew Russell．高级技术总监，Digital Reasoning System；《Doj0：The Definitive Guide》的作者（OReilly）