第1讲-简单的算法复杂度分析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第1讲-简单的算法复杂度分析课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 算法 复杂度 分析 课件
- 资源描述:
-
1、第第1 1讲讲 简单的算法复杂性分析简单的算法复杂性分析算法复杂性算法复杂性算法复杂性(算法复杂性(度度)是)是算法运行所需要的计算机资源的量算法运行所需要的计算机资源的量,需要需要时间资源的量称为时间资源的量称为时间复杂性时间复杂性,需要的空间资源需要的空间资源的量的量称为称为空间复杂性空间复杂性。算法分析的目的:算法分析的目的:设计算法设计算法设计出复杂性尽可能低的设计出复杂性尽可能低的算法算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者算法分析(算法分析(Algorithm Analysis):对算法所需要):对算法所需要的两种计算机资源的两种计算机
2、资源时间和空间进行估算时间和空间进行估算 时间复杂性(时间复杂性(Time Complexity)空间复杂性(空间复杂性(Space Complexity)算法效率的衡量方法算法效率的衡量方法p先写程序,直接观察结果先写程序,直接观察结果n同一算法,程序不同,运行时间不同同一算法,程序不同,运行时间不同n写代码太费事,如果写出来才发现很慢写代码太费事,如果写出来才发现很慢p不写程序,直接分析算法不写程序,直接分析算法n不不写程序,怎么知道运行时间?写程序,怎么知道运行时间?u用用“基本操作基本操作”数来衡量数来衡量n表达式很复杂怎么办?表达式很复杂怎么办?u渐进表示渐进表示算法(算法(1)分析
3、)分析sum:=0;for i:=1 to n do for j:=1 to n do sum:=sum+ai,j;p基本操作:加法基本操作:加法p忽略循环变量忽略循环变量i和和j的改变时间的改变时间p共共n2次基本操作次基本操作p时间复杂度为时间复杂度为n2算法(算法(2)分析)分析sum:=0;for i:=1 to n do begin fact:=1;for j:=1 to i do fact:=fact*i;sum:=sum+fact;endp 第第i次循环执行了次循环执行了i个操作个操作p 总时间复杂度为总时间复杂度为1+2+3+n=n(n+1)/2p 如果式子再长一点,怎么办?如
4、果式子再长一点,怎么办?比较两个算法比较两个算法p算法(算法(1)执行了)执行了f(n)=n2次基本操作次基本操作p算法(算法(2)执行了)执行了g(n)=n2/2次基本操作次基本操作p那个算法好呢?那个算法好呢?n算法(算法(2)好,因为)好,因为g(n)0,0,s.t.s.t.nn nn0 0,0,0 f(n)f(n)cg(n)cg(n)O记号表示的是一个渐进上界,有时也被非正式地用来描述渐进上确界。记为:f(n)=O(g(n),表示f(n)的阶不高于g(n)的阶。根据O的定义,容易证明它有如下运算规则:(1)O(f)+O(g)=O(max(f,g)(2)O(f)+O(g)=O(f+g)(
5、3)O(f)O(g)=O(fg)(4)如果g(n)=O(f(n),则O(f)+O(g)=O(f)(5)O(Cf(n)=O(f(n),其中C是一个正的常数(6)f=O(f)po的定义的定义o(g(n)=f(n)|c0,n c0,n0 00,0,s.t.s.t.nn nn0 0,0,0 f(n)cg(n)f(n)0,c 0,s.t.s.t.nn nn0 0,0,0 cg(n)cg(n)f(n)f(n)记号表示的是函数的渐进下界。记为:f(n)=(g(n),表示f(n)的阶不低于g(n)的阶。p的定义的定义(g(n)=f(n)|c 0,n c 0,n0 0 0,0,s.t.s.t.nn nn0 0,
6、0,0 cg(n)cg(n)0,0,s.t.s.t.nn nn0 0,0,0 c c1 1g(n)g(n)f(n)f(n)c c2 2g(n)g(n)记号表示的是函数的渐进上界和下界。记为:f(n)=(g(n),表示f(n)与g(n)同阶。f(n)=(g(n)当且仅当当且仅当f(n)=O(g(n)且且f(n)=(g(n)。算法算法(渐进渐进)时间复杂度时间复杂度,一般均表示为以下几种数量一般均表示为以下几种数量级的形式级的形式(n为问题的规模为问题的规模,c为一常量为一常量):(1)称为常数级称为常数级(logn)称为对数级称为对数级(n)称为线性级称为线性级(nc)称为多项式级称为多项式级(
7、cn)称为指数级称为指数级(n!)称为阶乘级称为阶乘级pP复杂度复杂度pNP复杂度复杂度pNPC复杂度复杂度算法复杂性分类算法复杂性分类简单算法的复杂性分析简单算法的复杂性分析对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本基本(或者说是主要或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如:例如:for(for(i i=1;i=1;i=n;+=n;+i i)for(j=1;j for(j=1;j=n;+j)=n;+j)c ci,ji,j=0;=0;for(k=0;
展开阅读全文