算法技术手册

当前位置:首页 > 网络编程 > 计算机理论基础知识 > 算法技术手册

出版社:东南大学出版社
出版日期:2009-4
ISBN:9787564116323
作者:[美]海涅曼 (Heineman.G.T.),[美]波利切 (Pollice.G.),[美]塞克欧 (Selkow.S.)
页数:343页

章节摘录

  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)

内容概要

  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

作者简介

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

图书封面


 算法技术手册下载 更多精彩书评



发布书评

 
 


精彩书评 (总计1条)

  •     看得英文版,不难懂。里面的算法伪代码和配套图示非常棒。比较奇怪的是排序里面没有提到归并,这个一般的算法书里面都会讲到。总之,作为一本快速查询算法的书籍,名副其实。就算你原来不懂的算法,看过了基本上也能理解。最多复杂度分析什么的可能需要一些更全面的书籍来解答。

精彩短评 (总计7条)

  •     很好的一个总结。而且算法的伪代码加上简单的配图实例,非常好。比较奇怪的是排序算法里面没有归并排序,一般的算法书上好像都会提这个的。
  •     挺不错的一本小册子, 很实用,很方便简单的温习一下当年的算法课
  •     影印版
  •     很不错的书, 适合我这种看到《算法导论》就头大的人, 适当量的推理, 对算法适用场合清晰的阐述,比较适合做案头书
  •     抽空找找回忆
  •     上学看过,复习挺好
  •     只要是奥莱离出版的,总是要找来几本翻翻看,这算法才叫实用!你索索你丫能在内存管理写内存缓冲区的时候用他妈强连通子图算法吗?
 

外国儿童文学,篆刻,百科,生物科学,科普,初中通用,育儿亲子,美容护肤PDF图书下载,。 零度图书网 

零度图书网 @ 2018