- 1、本文档共3页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法的含义
算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
特征
一个算法应该具有以下六个重要的特征:
算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
1、有限性
算法的有穷性是指算法必须能在执行有限个步骤之后终止;
2、确切性
算法的每一步骤必须有确切的定义;
3、输入
一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;
4、输出一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
算法复杂度分析
通常一个算法的复杂度是由其输入量决定的,随着输入的增加,复杂度越大。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
方法:
时间复杂度
(1)算法耗费的时间和语句频度
一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间
算法转换为程序后,每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。
若要独立于机器的软、硬件系统来分析算法的时间耗费,则设每条语句执行一次所需的时间均是单位时间,一个算法的时间耗费就是该算法中所有语句的频度之和。
(2)问题规模和算法的时间复杂度
算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
矩阵乘积问题的规模是矩阵的阶数。
一个图论问题的规模则是图中的顶点数或边数。
一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费,是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时,时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。
(3)渐进时间复杂度评价算法时间性能
主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
空间复杂度S(n)=O(f(n))
算法执行期间所需要的存储空间包括3个部分:
·算法程序所占的空间;
·输入的初始数据所占的存储空间;
·算法执行过程中所需要的额外空间。
Operating System 2.28.2013
Information Management Information System 12708
Instructor 王斌 陈佳威
第 1 页 共 3 页
您可能关注的文档
- 第四章电子表格Excel2003习题.doc
- 第四章营业税习题及答案.doc
- 第四章非金属及其化合物单元检测.doc
- 第四部分专题一自然环境对人类活动的影响.doc
- 第章平面连杆机构习题答案.doc
- 第章线性表及其应用习题解答.doc
- 第课虽有佳肴阅读欣赏题.doc
- 等级考试二级JAVA考点分析之APPLET程序设计.doc
- 等高线模式:解决极大极小问题的另类策略.doc
- 答案-2011~2012学年第二学期A卷南昌大学考试试卷标准格式.doc
- 2024年河北廊坊文安县京南文化旅游事业发展有限公司招聘工作人员4名笔试备考题库及答案解析.docx
- 2024年广州市白云区事业单位公开招聘工作人员68人笔试备考题库及答案解析.docx
- 2024年度黑河市市直事业单位公开选调工作人员13人笔试备考题库及答案解析.docx
- 2024年菏泽巨野县财金投资集团有限公司公开招聘工作人员补充笔试备考题库及答案解析.docx
- 2024年河北正定二五六医院招聘工作人员36名笔试备考题库及答案解析.docx
- 2024年甘肃兰州财经大学诚聘高层次人才补充(第四期)笔试备考题库及答案解析.docx
- 2024保定高碑店市招聘卫健局下属事业单位137名笔试备考试题及答案解析.docx
- 2024包头市眼科医院招聘笔试备考题库及答案解析.docx
- 2024年甘肃张掖民乐县招聘专职社区工作者、未就业普通高校毕业生到社区岗位服务、大学生村文书加试笔试模拟试题及答案解析.docx
- 2024年甘肃武威古浪县黄花滩镇选聘大学生村文书笔试备考试题及答案解析.docx
最近下载
- 绩效考核方案(经典通用~).doc
- 必威体育精装版版国有企业因公临时出国(境)管理办法.docx VIP
- 建筑工程图集 07J205:玻璃采光顶.pdf VIP
- 2024年长沙中考作文“考试的背后”审题指导+立意素材+范文8篇.docx
- 中医护理年度工作总结PPT.pptx
- 高考语文思辨类作文写作全面指导写作指导:二元思辨性作文速成模板及示例.pdf VIP
- 项目部安全隐患排查治理制度.docx
- 售楼处保洁服务标准-完整版.pdf VIP
- 《双减背景下小学语文高效课堂和有效教学模式研究》科研课题结题报告.docx
- 【精选 】高一年级(6)班《告别假努力,学会真自律》主题班会(28张PPT)课件.pptx
文档评论(0)