算法技術(shù)手冊(cè)

內(nèi)容概要

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

作者簡(jiǎn)介

　　George T.Heineman，Gary Pollice和Stanley Selkow均為 Woree ste r PolYteChniC In stitute（伍斯特理工學(xué)院）計(jì)算機(jī)科學(xué)系的教授。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.

媒體關(guān)注與評(píng)論

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

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法技術(shù)手冊(cè) PDF格式下載

---