算法分析-基础-02_persistenthuang的博客-程序员宅基地

技术标签: 算法  C++  

算法分析

定义:分析算法占用的计算机资源情况
目的:

  • 设计算法:设计出复杂度尽可能低的算法
  • 选择算法:选择复杂度最低的算法、

因数

算法的时间复杂性与问题的规模相关,是问题大小n的函数

时间复杂度

定义:算法运行所需要的时间资源的量
方法:

  • 事后实验统计法
  • 事前分析估算法:渐近分析

空间复杂度

定义:算法分析所需要的空间资源的量

渐近时间复杂度的含义:

当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

最坏情况下的时间复杂性和平均时间复杂性:

最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时,不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度,平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和。

渐近时间复杂度分析的一般步骤:

  • a. 决定用哪个(或哪些)参数作为算法问题规模的度量
  • b. 找出算法中的基本语句
    通常是最内层循环的循环体。
  • c. 检查基本语句的执行次数是否只依赖于问题规模
    如果基本语句的执行次数还依赖于其他一些特性,则需要分别研究最好情况、最坏情况和平均情况的效率。
  • d. 建立基本语句执行次数的求和表达式
    计算基本语句执行的次数,建立一个代表算法运行时间的求和表达式。
  • e. 用渐进符号表示这个求和表达式

三个渐近符号的含义:

  • 大O符号(<=)用来描述增长率的上界,当输入规模为n时,算法消耗时间的最大值。
  • 大Ω(>=)符号用来描述增长率的下界,当输入规模为n时,算法消耗时间的最小值。
  • 大θ(=)符号——渐近紧界记号,用来描述增长率的准确界。
  • 通常只求最坏情况运行时间,因为给出了任何输入的运行时间的上界。对某些算法,最坏情况经常出现“平均情况”往往与最坏情况一样差
    002

最优算法:

如果我们能够知道一个问题的计算复杂性下界,也就是求解这个问题的最少工作量,就可以较准确地评价该问题的各种算法的效率,进而确定已有的算法还有多少改进的余地。

递归方程:

003
004

递归树法:

005
006

主方法:

007
008

例题:

  1. 给定以下算法:
    long FN( long n )
    {
    if (n<=1)
    return 1;
    return n + FN(n-1);
    }
    该算法的时间复杂度为O( n )
  • 解:
    T(n)=T(n-1)+C=T(1)+nC=O(n)
  1. 求整数n(n≥0)阶乘的算法如下,请写出递归方程并给出求解过程。
    int fact(int n)
    { if(n<=1) return1;
    return n*fact(n-1);
    }
  • 解:
  • T(n)=nT(n-1)+c=O(n)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43309907/article/details/104570457

智能推荐

西部世界IPFS科普:什么是非对称加密?_通往未来的道路的博客-程序员宅基地

西部世界发现,在《想要安全地保管资产,先要知道钱包的这些知识》中,我们可以了解到在区块链的这些钱包中,公钥可以比作是银行账户,而账户地址类似于银行卡号,私钥可以被看成银行卡号以及银行卡密码的组合。这样一类比似乎对区块链中的私钥、公钥、地址这些名词有了比较清晰的认识,但是其实在这些名词的背后的理论支撑是非对称加密技术,它是什么样的技术呢,今天大白就给大家科普一下。一、对称加密是什么?首先,在讲非对称加密之前,先简单讲一下对称加密。对称加密也叫做单密钥加密,西部世界IPFS矿机加Mariobtc,指的是

2016年中总结_追梦的晓米的博客-程序员宅基地

时间飞快,2016年上半年中收获很多。。

如何写一个简单的解释器(Interpreter)-4_Runtime Error的博客-程序员宅基地

还记得Confucius说过什么吗?“我听说了,后来我忘记了”“我看到了,后来我记住了.”“我做过了,后来我理解了.”这一章我们讲讲多个乘数法的计算,注意除法是整数的除法,比如9除以4等于2。我还要使用一种新的表达方式,上下文无关的语法书(简称为语法书),或者叫BNF(Backus Naur样式),来表示一种编程语言的语句规则。多说一句,我用的是扩展的...

php xml解析方法_weixin_30698527的博客-程序员宅基地

XML处理是开发过程中经常遇到的,PHP对其也有很丰富的支持,本文只是对其中某几种解析技术做简要说明,包括:Xml parser, SimpleXML, XMLReader, DOMDocument。1。 XML Expat Parser:XML Parser使用Expat XML解析器。Expat是一种基于事件的解析器,它把XML文档视为一系列事件。当某个事件发生时,它调用一个指定的函数...

【vulnhub】---超级玛丽靶机_通地塔的博客-程序员宅基地

目录一、实验环境二、信息收集三、渗透测试  1、漏洞发现和利用  2、提权四、总结一、实验环境靶机:靶机(192.168.15.159)攻击机:kali Linux(192.168.15.129)二、信息收集主机发现命令:nmap -sn 192.168.15.0/24命令:netdiscover -i eth0 -r 192.168.15.0/24命令:arp-scan -l端口扫描命令:masscan --rate=10000 --ports 0-65535

随便推点

HTML制作手风琴效果,纯js和纯css+html制作的手风琴的效果_慕容圆月的博客-程序员宅基地

一:纯css+html的手风琴效果这种用css写的手风琴比较简单,主要是应用到css中的,transition属性。代码如下:body{background:url(‘bg.gif‘) repeat;}ul,li,p{margin:0px;padding:0px;list-style:none;}#div{width:1180px;height:405px;border:5px solid #cc...

loadView、viewDidLoad、viewWillAppear、viewDidAppear等详解_st646889325的博客-程序员宅基地

loadView; This is where subclasses should create their custom view hierarchy if they aren't using a nib. Should never be called directly.这是当他们没有正在使用nib视图页面,子类将会创建自己的自定义视图层。绝不能直接调用。viewDidLoad;

HDMI介绍与流程_白面小书生的博客-程序员宅基地

HDMI,全称为(High Definition Multimedia Interface)高清多媒体接口,主要用于传输高清音视频信号。 HDMI引脚:HDMI有A,B,C,D,E五种引脚类型,目前市面中比较常见的就是Type A:其中1-9 都是TMDS数据传输实际上用到的引脚,分为0,1,2三组10-12 为TMDS时钟信号,如当前Video T

python小括号报错_Python学习记录:括号配对检测问题_weixin_39844942的博客-程序员宅基地

Python学习记录:括号配对检测问题一、问题描述在练习Python程序题的时候,我遇到了括号配对检测问题。问题描述:提示用户输入一行字符串,其中可能包括小括号 (),请检查小括号是否配对正确,配对成功与否分别输出:配对成功!配对失败!其中,小括号配对要考虑配对顺序,即()表示配对,)(不是配对,只考虑小括号配对。一提起括号配对,我们可能会想到C语言正则表达式计算的符号优先级问题,在C语言中我们通...

js计算时间差,天、时、分、秒_Mick_小马哥的博客-程序员宅基地

function getTimeDiff(_startTime, _endTime) { let startTime = new Date(_startTime.replace(/-/g, '/')); let endTime = new Date(_endTime.replace(/-/g, '/')); let diff = endTime.getTime() - startTime.g...

我为什么要学习法律?_weixin_30538029的博客-程序员宅基地

我为什么要学习法律? 穿过所有岁月的沧桑,我终不忘年少的初心。 我为什么要学习法律,思来想去,不为名、权、利,就为自己一天比一天活得潇洒一点点。 从小就是学渣,不是不喜欢学习,而是跟不上,跟不上老师的节奏,跟不上就会懒散,然后就开始怀疑人生,自己到底行不...

推荐文章

热门文章

相关标签