- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
算法(algorithm)可以被定义为一个良定的计算过程,它具有一个或者若干输入值,并产生一个或者若干输出值。人们采用一般术语陈述问题,确定输入/输出关系,而算法则是描述这种输入/输出关系的特定计算过程。算法正确性:对每一个输入实例算法都能终止,并给出正确输出。算法正确性有两个要素;1是能够终止。2是结果正确。算法
算法设计和分析的步骤可概括:(1)问题的陈述。(2)模型的选择。(3)算法的设计。(4)算法的程序实现。(5)算法分析。
有穷性。一个算法在执行有穷个计算步骤后必须停止。可行性。算法中要执行的每一个计算步骤都是可以在有限时间内做完的。可行性、有穷性和确定性是相容的。输入。一个算法一般都要求一个或多个输入信息。输出。一个算法一般有一个或多个输入信息。它们通常可以被解释成为“对输入的计算结果”。确定性。一个算法中给出的每一个计算步骤,必须是精确的定义、无二义性的。算法具有以下五大特性
1初始:在循环的第一次迭代之前,循环不变式为真。2维持:如果在循环的某次迭代之前循环不变式为真,那么在下一次迭代之前,循环不变式仍然为真。3终止:当循环终止时,循环不变式给出有用性质,这个性质可以用于证明算法的正确性循环不变式具有以下三个性质:
01循环不变式:A[j]是A[j..Length[A]]中的最小元素。循环不变式:在1~4行外层for循环的每次迭代开始,子数组A[1..i-1]中的元素有序。02
算法分析(p4)算法分析(p4)算法分析是指对一个算法所需的计算资源进行预测。考虑算法的好坏主要有以下几点:(1)执行算法所耗费的时间。(2)执行算法所耗费的存储空间,其中主要考虑辅助存储空间。(3)算法应易于理解,易于编码,易于调试等。最重要的计算资源是时间和空间资源(存储器)输入规模是输入元素的个数、用二进制表示的输入的总位数、和用图中顶点数和边数表示输入。一个算法的运行时间是指在某个输入时,算法执行基本操作的次数或者步数。
程序的输入。由编译系统所产生的代码程序的质量。执行程序的计算机机器指令的性能与速度。程序所依据的算法的时间复杂度。2、影响程序运行时间的主要因素:空间复杂度时间复杂度3、算法的复杂性测度主要有两个方面:
算法最坏情况下的运行时间,即对于规模n的任何输入,算法运行最长的时间。之所以这样,是由于以下三个原因:算法的最坏情况运行时间是任一输入运行时间的上界。对于某些算法,最坏情况经常出现。算法的“平均情况”性能常常与最坏情况大致相同。最坏情况和平均情况分析(P6)
渐近表示(P8)渐进表示:是方便地表示算法的最坏情况下,计算的复杂度。三个定义,三例题。定义1.1如果存在三个正常数
第2章分治法递归(P13)递归程序可被简单地定义为对自己的调用。递归程序要求必须有终止条件。斐波那契(Fibonacci)序列。替换方法(P16)用替换方法解某个递归方程时,分为两步。首先猜测问题解的某个界限,然后用数学归纳法证明所猜测解的正确性。主方法(P18)主定理(三种情况,三个例题)
分治法的基本思想(p20)分治法在每一层递归上由三个步骤组成:划分(divide):将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。解决(conquer):若子问题规模较小,则直接求解;否则递归求解各子问题。合并(combine):将各子问题的解合并为原问题的解。
算法思想如果我们将分治策略用于此问题,每次将问题分成大致相等的两部分,分别在这两部分中找出最大值与最小值,再将这两个子问题的解组合成原问题的解,就可得到该问题的分治算法。归并排序算法(P28)归并排序的关键操作是归并两个已排序的子序列的过程。找最大值与最小值分治算法
归并排序最坏情况下的时间复杂度Θ(nlbn)要优于冒泡排序最坏情况下的时间复杂度Θ(n2)。
动态规划(dynamicprogramming)已经成为计算机科学中重要的算法设计范型。01提出:1957年,RichardBellman在描述一类优化控制问题时创造了这个名字。02作用:那时,这个名字更多地用于描述问题,而不是解问题的技巧。03动态规划(P49)
特点:此方法的主要特点是通过采用表格技术。计算所有子问题的解。计算的过程从小问题到大问题,并将计算结果存储在一张表中。1优点:一旦一个子问题被解决,就存储其结果,此后遇到同样的子问题,就不再重复计算。用多项式算法代替指数算法。2
应用:动态规划典型的应用领域是组合优化问题。在这类问题中,可能会有许多可行解(feasiblesol
文档评论(0)