第1讲-简单的算法复杂度分析课件.ppt
《第1讲-简单的算法复杂度分析课件.ppt》由会员分享,可在线阅读,更多相关《第1讲-简单的算法复杂度分析课件.ppt(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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,s.t.nn0,s.t.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)(3)O(f)
5、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,s.t.nn0,s.t.nn0 0,0,0 f(n)cg(n)f(n)0,s.t.nn,c 0,s.t.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,s.t.nn 0,s.t.nn0 0,0,0 cg(
6、n)cg(n)0,s.t.nn0,s.t.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)称为多项式级称为多项式级(cn)称为指数级
7、称为指数级(n!)称为阶乘级称为阶乘级pP复杂度复杂度pNP复杂度复杂度pNPC复杂度复杂度算法算法复杂性分类复杂性分类简单算法简单算法的复杂性分析的复杂性分析对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基基本本(或或者者说是是主主要要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如:例如:for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=0;k=n;+k)ci,j=ci,j+ai,k*bk,j;最大连续和最大连续和p给一串整数给一串整数a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 算法 复杂度 分析 课件
限制150内