书签 分享 收藏 举报 版权申诉 / 33
上传文档赚钱

类型算法与设计算法分析基础-整体框架-课件.ppt

  • 上传人(卖家):三亚风情
  • 文档编号:3524966
  • 上传时间:2022-09-11
  • 格式:PPT
  • 页数:33
  • 大小:308KB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《算法与设计算法分析基础-整体框架-课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    算法 设计 分析 基础 整体 框架 课件
    资源描述:

    1、2022-7-2422007-2008-01Design and Analysis of AlgorithmsSCUECReview of last classbHow to solve a problem by computerbThe notion of algorithm Actual problem Mathematics model Algorithm design and analysis Programming Result analysis Input output finiteness effectiveness definitenessbAlgorithm design p

    2、attern2022-7-2432007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?bNatural language Step1 Input m and n.Step2 Divide m by n and assign the value of the remainder to r.Step3 If r=0,return the value of n as the answer and stop;otherwise,proceed to Step 4.Step4 Assign the v

    3、alue of n to m and the value of r to n.Step5 Go to Step2.Advantages:easy understandDisadvantages:exist inherent ambiguity2022-7-2442007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?(II)bFlow chartStartr=0Input m and nr=m%nm=nn=routput nStopA flowchart is a method of expr

    4、essing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithms steps.Advantages:intuitiveDisadvantages:lack flexibility2022-7-2452007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?(III)bProgramming languageAdvantages:can run on

    5、 computer directly Disadvantages:lack abstraction#include int GCD(int m,int n)int r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;void main(void)cout GCD(60,24)0,then f(n)=(g(n)f(n)=2n3+3n-5=(n3)f(n)=2n4+1=(n3)?()()limf ng nnc2022-7-24282007-2008-01Design and Analysis of AlgorithmsSCUECAsymptotic Notation:f

    6、(n)=(g(n)nf(n)c2g(n)n0c1g(n)2022-7-24292007-2008-01Design and Analysis of AlgorithmsSCUECOrders of growth of some important functionsbAll logarithmic functions loga n belong to the same class (log n)no matter what the logarithms base a 1 isbAll polynomials of the same degree k belong to the same cla

    7、ss:aknk+ak-1nk-1+a0 (nk)bExponential functions an have different orders of growth for different as2022-7-24302007-2008-01Design and Analysis of AlgorithmsSCUECBasic asymptotic complexity classesfactorialn!exponential2ncubicn3quadraticn2n-log-nn log nlinearnlogarithmiclog nconstant12022-7-24312007-20

    8、08-01Design and Analysis of AlgorithmsSCUECAsymptotic Notation:obo-notation Call f(n)=o(g(n)if there exist positive constants c and n0 such that f(n)cg(n)for all n n0.Or,if ,then f(n)=o(g(n)f(n)=2n3+3n-5=o(n4)f(n)=o(g(n)if and only if f(n)=O(g(n),but g(n)O(f(n)nlogn=o(n2)means that nlogn=O(n2),but n2 O(nlogn)()()lim0f ng nn2022-7-24322007-2008-01Design and Analysis of AlgorithmsSCUECAsymptotic Notation Using the o-notation,we can concisely express the following hierarchy of complexity classes.bPolynomial complexity classes:1 logn n nlogn n2 1)n!nnThe End

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:算法与设计算法分析基础-整体框架-课件.ppt
    链接地址:https://www.163wenku.com/p-3524966.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库