算法优劣的评估和程序设计基本方法.doc_第1页
算法优劣的评估和程序设计基本方法.doc_第2页
算法优劣的评估和程序设计基本方法.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法优劣的评估和程序设计基本方法一、使用循环结构，必须预先估计程序的时间复杂度。估计方法如下：（1）只执行一次的语句，操作时间忽略不计。（2）对循环结构中的所有操作，则必须能少则少，能放在循环外面进行的操作坚决放在外面；对于多次计算的表达式，坚决只计算一次用变量保存起来。循环的初值和终值能少就少，O（循环次数），一般忽略循环内部的语句数。（3）循环次数不定时，一般取最大可能的循环次数。（4）对嵌套的循环，则计为O（外层循环次数*内层循环次数）。因此，减少循环的嵌套层数，对程序的优化有极大的效果。（5）时间复杂度的计算，一般只取最高的一项的数量级，例如：程序段一；O(n)程序段二；O(n2)程序段三；O(n3)程序段四；O(1000n2)程序段五；O(10000n)一般计为：O(n3)，n250时能够接受，超过250非常容易超时。（6）计算出程序的时间复杂度后，再根据题目所给的数据规模（即n的大小），算出复杂度值，一般O(1千万)左右是可以接受的。（7）算法的优劣顺序：O(0)用数学方法直接结果直接输出的算法O(1)用数学方法推出公式，数据带入公式得结果O(n)一重循环穷举法O(nlogn)对树形数据结构的维护和搜索O(n2)二重循环或对图的数据结构的搜索O(n3)三重循环二、程序设计的基本步骤：（1）审题，弄懂题目的全部意思。（2）建立数学模型。即用什么样的数学方法能解决题目的问题。（3）选择恰当的数据结构。包括选择合适的数据类型、数据组织方式。（4）设计算法。（5）对所设计的测算时间复杂度（6）如果时间复杂度在所给数据规模内能够实现（即1秒能完成），编程实现算法。（能的满分）（7）如果时间复杂度在所给的数据规模内无法实现，优化算法，尝试减少循环层数和循环次数。（8）算法通过优化能达到要求，编程实现。（能得满分）（9）算法通过优化不能达到要求，如能更换算法，即想出其它更好的算法，返回（4）重做。（10）如更换不了算法，在现有算法内尽可能优化
人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论