1 / 15
文档名称:

时间复杂度分析.ppt

格式:ppt   大小:11,004KB   页数:15页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

时间复杂度分析.ppt

上传人:s1188831 2017/8/9 文件大小:10.75 MB

下载得到文件列表

时间复杂度分析.ppt

相关文档

文档介绍

文档介绍:时间复杂度分析
什么是时间复杂度?
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。
如何计算?
计算时间复杂度的过程,常常需要分析一个算法运行过程中需要的基本操作,计量所有操作的数量。
各种时间复杂度
O(1)<O(logn)<O(n1/2) <O(n) < < O(nlogn) <O(n×n1/2)< O(n2)<O(n3) < O(2n) < O(n!) < O(nn)
O(1)(常数时间)
不受数据规模的影响
例子:判断一个数的奇偶
O(logn)
数据规模不断减半
例子:二分查找
给定一个长度为n的有序序列A[0],A[1],A[2]...A[n],询问一个数num在序列中的位置
int L=0,R=n-1;
while(L<=R)
{
int mid=(L+R)/2;
if(a[mid]>=num) R=mid-1;
else L=mid+1;
}
printf("%d\n",L);
O(n1/2)
例子:判断一个数是否是素数
for i=2 to sqrt(n) 依次判断是否能够整除n即可
O(n)
又叫做线性时间复杂度
例子:给定一个长度为n的序列,求最大值
O(nlogn)
例子:对一个长度为n的无序序列A排序
归并排序大致框架
merge-sort(A,L,R)
if L<R
then MID=(L+R)/2
merge-sort(A,L,MID)
merge-sort(A,MID+1,R)
merge(A,L,MID,R)

最近更新

芪参虫草酒传统工艺现代化-全面剖析 35页

影视制作伦理探讨-全面剖析 35页

连续流动分析仪测定水环境中挥发酚的研究 3页

进一步加强基层央行专业技术人才队伍建设的思.. 3页

数据加密与安全策略-全面剖析 33页

过程能力指数在化探样品分析质量评估中的应用.. 3页

高尔夫专卖店出租合同(3篇) 7页

辅助器材在篮球训练中的应用现状及发展对策探.. 3页

车铣加工中心铣螺纹宏程序的应用 3页

记忆原理及方法 69页

议论文巧设分论点llh 64页

超声多普勒水连续油水分散流流速测量方法 4页

资产重组的市场反应——1997 年沪市资产重组实.. 3页

认知升级第一原理part1刻意练习(一) 78页

负荷预测在县级电网规划中的应用 4页

语言经济学视域下理工类研究生外语复合型人才.. 5页

试油过程中的油气层保护技术研究 3页

论仿射不变特征和空间技术特点的图像检索分析.. 3页

计算机智能仿真技术在印制电路板镀铜工艺中的.. 4页

解决细纱机长车龙筋变形方法浅析 3页

装备制造业三维作业指导应用研究 3页

行政事业单位会计内部控制的现状及其完善对策.. 3页

蝴蝶式多层悬臂梁压电发电装置研究 3页

薄板烘丝机自动控制系统中的PLC技术分析 3页

营改增对港口企业的影响与对策 3页

茶多酚对运动员健康体适能的影响研究 3页

节能材料在房屋建筑工程施工中的应用研究 4页

2025年度个人住宅水电安装与安全风险评估承包.. 8页

2025年度专业保洁团队保洁员劳动合同 7页

2025年家长学校学生安全教育与责任协议 7页