Markdown编辑器 希腊字母 程序栈 ipv4 database class flash flexbox pip Semantic UI vue引入组件 vue提交表单 mac虚拟打印机 mysql小数用什么类型 linux重启mysql python数据 python获取日期 python怎么调用函数 python平台 java的string javaswitch语句 java表达式 java时间格式化 java的框架 java数据类型转换 php项目实例 登录界面html sql综合利用工具 嵌入式linux驱动程序设计从入门到精通 黑帮之地修改器 stata软件 51脚本 pyh 完美手游模拟器 findall cubase下载 视频md5修改器 vs2012中文旗舰版下载 edquota alert换行
当前位置: 首页 > 学习教程  > 编程语言

算法笔记摘抄

2020/8/11 18:45:36 文章标签:

1、算法的特征:输入输出、有穷性、确定、可行。

算法可以没有输入,但是一定有输出。

有穷性:算法在执行有限的步骤之后,自动结束不会出现无限循环,并且每个步骤在一个可接受的时间内完成。不是数学意义上的有穷,而是实际应用中合理的、可接受的边界。

确定:指算法的每个步骤都有确定的含义,不会出现二义性。相同的输入只能有唯一的输出结果。

可行:算法的每个步骤都是可行的,也就是说,每一步都可通过执行有限的次数完成。

2、算法的设计要求:可读、正确、健壮、执行效率高存储少。

正确:算法的输入输出、加工处理无歧义,能正确的反应问题的需求,能得到问题的正确答案。

正确性的4个层次:算法执行不出错;算法对合理的输入输出正确的答案;算法对非法输入有满足规格说明的输出;算法对精心选择的刁难的测试数据有满足要求的输出。

可读:算法设计的一个目的就是便于便于阅读、理解和交流。可读是算法好坏很重要的标志。

健壮:当输入非法数据,算法也应该做出相关处理,不应该产生异常或莫名其妙的结果。

时间效率高存储量低是好算法应该具备的特点。

3、算法效率的度量方法:事后度量法和事前分析估算方法。事后度量是先设计好程序和测试数据,依靠计算机的计时对不同算法执行时间比较,确定算法时间效率。

一个高级程序语言编写的算法在计算机上的时间效率取决于:算法的策略方法;软件编译的代码质量;问题的输入规模;机器执行指令的速度;

问题输入规模指:输入量的多少。

在分析程序执行时间时:最重要 的是把程序看做是独立于程序设计语言的算法或者一系列步骤。

在分析算法的运行时间时,要把基本操作的数量和问题的输入规模关联起来,即基本操作的数量必须表示成输入规模的函数。

如对n求累加和,输入是n,操作数量是f(n);又如输入坐标(x,y),操作数量是f(x,y)。

4、函数的渐进增长:给定两个函数f(n),g(n),当n>=N时,总有f(n)>=g(n),则对应n>=N,f(n)的渐进快于g(n).

5、算法时间复杂度:在进行算法分析时,语句的总执行次数T(n)是关于输入规模n的函数,分析T(n)的随n的变化情况并确定n的数量级。算法的时间复杂度,也就是算法的时间量度,记做:T(n)= O(f(n)).它表示随着问题规模n的增大,T(n)和f(n)的增长率是一个量级,称作算法的渐进时间复杂度,简称时间复杂度。f(n)是问题规模n的某个函数。

6、推导大O阶方法:用1取代运行时间中的所有加法常数;在修改后的运行函数中,只保留最高阶项;最高阶项存在且系数非0,则去除与这个项相乘的常数。

举例:T(n) = nlog2(n/2)+n^2.+4n+3,—》nlog2(n/2)+n^2.+4n+1--》n^2--》O(n^2)

常见的时间复杂度排序:O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

7最坏情况:我们提到的运行时间一般都是最坏时间

平均时间:期望的运行时间,最有实际意义。

 


本文链接: http://www.dtmao.cc/news_show_100019.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?