算法技術手冊

內容概要

　　創(chuàng)造穩(wěn)定的軟件需要有效的算法，但是程序設計者們很少能在問題出現(xiàn)之前就想到?！端惴夹g手冊（影印版）》描述了現(xiàn)有的可以解決多種問題的算法，并且能夠幫助你根據需求選擇并實現(xiàn)正確的算法——只需要一定的數(shù)學知識即可理解并分析算法執(zhí)行。相對于理論來說，本書更注重實際運用，書中提供了多種程序語言中可用的有效代碼解決方案，可輕而易舉地適合一個特定的項目。有了這本書，你可以：　　解決特定編碼問題或改進現(xiàn)有解決方案的執(zhí)行；　　迅速確定與需要解決的問題相關的算法，并判定為什么這樣的算法是正確的；　　探索C、C++、Java、Ruby中的算法解決方案，伴有實現(xiàn)訣竅；　　了解一個算法預期的執(zhí)行情況及最佳的執(zhí)行條件；　　發(fā)現(xiàn)不同算法中相似設計產生的沖突；　　學習先進的數(shù)據結構以改進算法效率?！　∮辛恕端惴夹g手冊》，你可以學習如何改進算法的性能，這是軟件應用成功的關鍵。

作者簡介

　　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

章節(jié)摘錄

　　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.

媒體關注與評論

　　“作者汲取了大量鮮為人知的文獻資料，這本不可或缺的指南鞏固了理論與實際操作的完美平衡。通過它來理解算法變得更加輕松容易?！薄　　狹atthew Russell．高級技術總監(jiān)，Digital Reasoning System；《Doj0：The Definitive Guide》的作者（OReilly）

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法技術手冊 PDF格式下載

---