算法分析-基础-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

智能推荐

关于字符数组以及字符串数组_一尾鱼汤的博客-程序员宅基地

例题13://13.编写一程序,将两个字符串连接起来,结果取代第一个字符串(mark下来加深印象),加油加油加油!(1)自己编写一个strcat函数int main(){ int strcat(char a[100],char b[100]); char a[100]={0}, b[100]={0}; //初始化字符数组; int i=0,j=0; cout&lt;&lt;"请输入两个字符串:"; cin&gt;&gt;a&gt;&gt;b;

Python配置Qt Designer与PyUIC_热心市民付先生的博客-程序员宅基地_python pyuic

Python配置Qt Designer与PyUIC安装pyqt相关包pip install pyqtpip install pyqt5-toolsPyCharm中选择相应的python解释器3. 添加外部工具名称填写自己方便易记得即可,我的名称添加为QTDesigner程序选择designer.exe,位置为当前解释器路径下的Lib\site-packages\pyqt5-tools\designer.exe工作目录为当前项目文件的目录添加选择完毕界面为:确定即可,再次

关于WebSocket_彪彪_的博客-程序员宅基地

原文链接:https://www.liaoxuefeng.com/wiki/1022910821149312/1103303693824096WebSocket是HTML5新增的协议,它的目的是在浏览器和服务器之间建立一个不受限的双向通信的通道,比如说,服务器可以在任意时刻发送消息给浏览器。为什么传统的HTTP协议不能做到WebSocket实现的功能?这是因为HTTP协议是一个请求-响应协议,...

FineUI初学手册_star_2008_的博客-程序员宅基地

女朋友鄙视我原创少...1.下载 进入官方论坛:http://www.fineui.com/bbs/要用到下载源代码和空项目下载http://fineui.codeplex.com/http://fineui.com/bbs/forum.php?mod=viewthread&tid=2123源代码直接下载,注意FineUI版本空项目里下载 对应版本的空项

NSStringDrawingOptions_yinachong的博客-程序员宅基地

NSStringDrawingTruncatesLastVisibleLine:如果文本内容超出指定的矩形限制,文本将被截去并在最后一个字符后加上省略号。如果没有指定NSStringDrawingUsesLineFragmentOrigin选项,则该选项被忽略。NSStringDrawingUsesLineFragmentOrigin:绘制文本时使用 line fragement or

随便推点

HTML5 APP----2014年H5没火,why?2016年H5能火,why?_谷震平的博客-程序员宅基地

0 前言        HTML5做跨平台的APP,在大多数人的脑子里没有什么好感,我身边的朋友也这么说。Anyway,我用完以后得出这样的结论:HTML5跨平台APP开发,在2015年以后会越来越火。    在2014年以前,HTML5的性能和能力都不够充足。特别是性能,因为Android4.4以下版本不能支持webGL技术,所以大部分低端Android手机无法流畅运行手机APP。D

Chromium多进程架构初探-兼谈Android平台版本_coloriy的博客-程序员宅基地

Chromium以多进程架构著称,它主要包含四类进程,分别是Browser进程、Render进程、GPU进程和Plugin进程。之所以要将Render进程、GPU进程和Plugin进程独立出来,是为了解决它们的不稳定性问题。也就是说,Render进程、GPU进程和Plugin进程由于不稳定而引发的Crash不会导致整个浏览器崩溃。本文就对Chromium的多进程架构进行简要介绍,以及制定学习计划。

Mybatis源码分析_风铃峰顶的博客-程序员宅基地

实例import org.apache.ibatis.io.Resources;import org.apache.ibatis.session.*;import org.junit.Before;import org.junit.Test;import java.io.IOException;import java.io.InputStream;import java.util.ArrayList;import java.util.List; private SqlSessionF

Composer常见问题汇总_cicibi6696的博客-程序员宅基地

问题一: [Composer\Downloader\TransportException] ...

什么时候不能使用箭头函数_一水茶缘YY的博客-程序员宅基地

共 2670 字,读完需 5 分钟。编译自 Dmitri Pavlutin 的文章,对原文内容做了精简和代码风格优化。ES6 中引入的箭头函数可以让我们写出更简洁的代码,但是部分场景下使用箭头函数会带来严重的问题,有哪些场景?会导致什么问题?该怎么解决,容我慢慢道来。能见证每天在用的编程语言不断演化是一件让人非常兴奋的事情,从错误中学习、探索更好的语言实现、创造新的语言特性是推动编程语言版本迭代的动