文档介绍：该【数据结构和算法 算法和复杂 】是由【niuwk】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【数据结构和算法 算法和复杂 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法和复杂度
1/22
算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
一个算法通常具有五个重要特性:
有穷性有穷步结束
确定性唯一执行路径
可行性可以通过基本运算实现
输入零个或多个输入
输出一个或多个输出
非数学有穷性!
算法和算法复杂度
第1页/共22页
算法和复杂度
2/22
算法和数据结构是两个不可分割的统一体
程序=数据结构+算法
数据结构通过算法实现操作
算法根据数据结构设计程序
第2页/共22页
算法和复杂度
3/22
算法设计的要求:
正确性正确反映需求(通过测试)
可读性有助于理解、调试和维护
健壮性完备的异常和出错处理
高效率与低存储的需求时间、空间的要求
第3页/共22页
算法和复杂度
4/22
算法效率的衡量方法1
事后统计
利用计算机内记时功能。
缺点:
必须先运行依据算法编制的程序;
所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣
第4页/共22页
算法和复杂度
5/22
算法效率的衡量方法2
事前分析估计
一个高级语言程序在计算机上运行所消耗的时间取决于: 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度
时间复杂度和空间复杂度
第5页/共22页
算法和复杂度
6/22
算法的时间度量
从算法中选取一种对于研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法执行的时间度量。
例,
for(j=1;j<=n;j++)
X=X+1;
for(i=1;i<=n;i++)
(c)
for(i=1;i<=n;i++)
X=X+1;
(b)
X=X+1;
(a)
基本操作重复执行的次数分别为1,n,n2
第6页/共22页
算法和复杂度
7/22
算法复杂度
问题的规模(n):或大小。如:矩阵的阶数、图的结点个数、被分类序列的正整数个数……
时间复杂度:算法的所需的时间和问题规模的函数。记为T(n)。当n->∞时的时间复杂性,被称之为渐进时间复杂度。
空间复杂度:算法的所需的空间和问题规模的函数。记为S(n)。当n->∞时的时间复杂性,被称之为渐进空间复杂度。
第7页/共22页
算法和复杂度
8/22
给定两个正值函数f和g,考虑以下定义:
定义1:
如果存在正数c和N,对于所有的n≥N,有f(n)≤cg(n),则f(n)=O(g(n))。
上述定义表明,如果对于足够大的n,或大于某自然数N的n,存在正数c,使f不大于cg,则f是g的大O符号。
大O符号
第8页/共22页
算法和复杂度
9/22
例如:f(n)=2n2+3n+1=O(n2)
在这里,g(n)=n2,c和N的可选值如表所示:
表对于函数f(n)=2n2+3n+1=O(n2),根据大O定义计算得到的c和N的不同值
N12345…∞
c≥6≥≥≥≥…
大O符号
第9页/共22页
算法和复杂度
10/22
算法分析中常见的复杂度
O(1)<O(lgn)<O(n)<O(nlgn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
常数对数多项式指数
复杂度举例
第10页/共22页