算法分析及分析实例-程序员宅基地

技术标签: 数据结构与算法  

He calculated just as men breathe, as eagles sustain themselves in the air.
                                                                             - Francois Arago
对算法估计的熟练程度要如同人们称赞大数学家欧拉一样,计算如同呼吸。

 

算法分析的主要任务为 算法正确性分析 算法复杂度分析。而我们主要讨论算法复杂度分析方法。

一.大O记号

在分析算法之前我们要了解大O记号的作用。大O记号是算法复杂度分析的利器。

对一个特定算法,我们可以用T(n)来表示算法处理数据规模为n时所消耗的时间(n>>2)(如图1-1,横轴n表示输入规模,纵轴f(n)表示消耗时间。)

                  (图1-1)

而大O就是T(n)的上届渐进。T(n) = O(f(n))且有 c>0,当n >> 2 后,有T(n) < c * f(n) .  如下图T(n)到O(f(n)):

O(f(n))和T(n)的比较可以通过图1-2看出:

                  (图1-2)

与T(n)相比,虽然不那么精确但是O(f(n))更加简洁,更能反映时间的增长趋势。

与大O记号性质类似,还有反映T(n)趋势的两种记号分别是Θ(f(n))和Ω(f(n)),他们则分别是T(n)的平均渐近和下届渐近。如图1-3:

 

                   (图1-3)

 

既然我们已经掌握了大O记号的使用,那我们可以来总结一下大O表示的常见复杂度。

O(1)  常数复杂度(含RAM模型基本操作)

O(n)  线性复杂度

O(n^c)  多项式复杂度包括O(n)

O(2^n)  指数复杂度(被认为难解的,随n增长极快)

从O(n^c)到O(2^n),是从有效算法到无效算法的分水岭。note:很多问题的O(2^n)算法容易设计出,但是O(n^c)的算法却很难设计出,甚至肯无法设计出。

各种复杂度比较:如图1-4

 

                (图1-4)

 

二.算法分析

为分析某一特定算法,再掌握了大O记号这个复杂度分析工具的使用后,我们需要了解复杂度分析的方法:

复杂度分析的主要方法:

  • 迭代:级数求和
  • 递归:递归跟踪 + 递推方程
  • 猜测 + 验证

 几类级数用于算法中迭代的复杂度分析:

算数级数(与末项平方同阶):T(n) = 1+2+3........+n = n(n+1)/2 = O(n^2)

幂方级数(比幂次高出一阶):T(n) = 1^2 + 2^2 +.......+n^2 = n(n+1)(2n+1)/6 = O(n^3)

几何级数(a > 1):与末项同阶 T(n) = a^0 + a^2 + .......+a^n = (a^n+1  - 1)/(a - 1) = O(a^n)

收敛级数:1/1/2 + 1/2/3 + 1//4 + .......... + 1/(n-1)/n = 1 - 1/n = O(1)

 调和级数:h(n) = 1 + 1/2+1/3+..........+1/n = O(logn)

 对数级数:log1+log2+log3+...........+logn = log(n!) = O(nlogn)

 举栗子利用算数级数分析循环(迭代)复杂度:

栗子1:

for(int i=0; i < n; i++)
for(int j=0; j < n; j++)
    ................//其他操作

算数级数:n+n+n+.......+n = n * n = O(n^2).得出此循环复杂度为O(n^2).

 栗子2:

for(int i=1; i < n; i << 1)
for(int j=0; j < i; j++)
            ..........其他操作

几何级数:1+2+4+.........+2^|_log2(n-1)_| = 2^[log2n] - 1 = O(n)

三.实例分析:

插入排序 复杂度分析:

#include <iostream>
using namespace std;
#include <vector>
class project{ public: void xzpx(){ for(int i=1; i<a.size(); i++){ key = a[i]; int j=i-1; while(j>=0 && a[j]< key){ a[j+1] = a[j]; j--; } a[j+1] = key; } } project(){} int key; vector<int> a={ 5,2,4,6,1,3}; }; int main() { project p; p.xzpx(); for(auto i:p.a){ cout << i << endl; } return 0; }

算数级数,一眼飘过去复杂度是O(n^2)

归并排序复杂度分析:

#include <stdio.h>
using namespace std;

void merge( int a[] , int left , int middle , int right ){
    int l_len = middle - left;
    int r_len = right - middle - 1;
    int l_a[l_len];
    int r_a[r_len];
    int i,j,k=left;
    for( i = 0 ; i <= l_len; i++ )
        l_a[i] = a[i+left];
        
    for( j = 0 ; j <= r_len ; j++)
        r_a[j] = a[j+middle+1];
      
    i = 0;j = 0;
    while( i <= l_len && j <= r_len )
    {
        if( l_a[i] < r_a[j] )
            a[k++] = l_a[i++];
        else
            a[k++] = r_a[j++];
    }
    while( i <= l_len )
        a[k++] = l_a[i++];
    while( j <= r_len )
        a[k++] = r_a[j++];
}

void merge_sort( int a[] , int left , int right ){
    int middle;
    if( left < right )
    {
        middle = ( left + right ) / 2;
        merge_sort( a , left , middle );
        merge_sort( a , middle+1 , right );
        merge( a , left , middle , right );
    }
}

int main(){
    int a[]={
    5,4,3,2,1};
    merge_sort(a,0,4);
    for(int i=0; i<5; i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

归并排序递推式: T(n) = c (n=1) || 2T(n/2) + cn (n>1)

递推式无法求解,需要结合递推跟踪分析:

可以分析出只有合并的时候才费时间,并且每层所有合并共消耗cn,而一共log2n+1层。所以耗时cn(log2n+1),即O(n*logn),相比插入排序的O(n^2)复杂度要好。 

 

感觉迭代的算法分析交常见吧。也容易分析些。

 

图片来源:学堂在线《数据结构(上)》

转载于:https://www.cnblogs.com/HonkerYblogs/p/10581264.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34418883/article/details/94295190

智能推荐

《UNIX环境高级编程》学习环境搭建---apue.h_dirent 安装-程序员宅基地

文章浏览阅读404次。《UNIX环境高级编程》学习环境搭建—apue.h正式开始学习《APUE》,跟着学习的过程中也动手实践一下,所使用的操作系统为Ubuntu18.04基本步骤在官网上下载书中源代码tar -zxvf src.3e.tar.gzcd apue.3emake可能会出现以下错误/usr/bin/ld: 找不到 -lbsdcollect2: error: ld re..._dirent 安装

idea中ssm(spring-spring mvc-mybatis)框架搭建_ssm项目前端模块在哪-程序员宅基地

文章浏览阅读4.5k次,点赞2次,收藏5次。我的idea是13.1.3首先点击 File - New Project - 选择maven ,并且在右面选择maven-archtype-webapp选项,如图所示点击next后,出现填写GroupId和Artifactid,一般GroupId写com.***.项目,Artifactid写你的项目名称然后点击next点击nextProject _ssm项目前端模块在哪

Ubuntu18.04安装ROS Melodic(解决网络原因,先将所需压缩包下载到本地,然后rosdep update)_ubuntu18.0ros下载-程序员宅基地

文章浏览阅读3.1k次,点赞18次,收藏45次。Ubuntu18.04安装ROS Melodic(解决网络原因,先将所需压缩包下载到本地,然后rosdep update)一、ROS介绍机器人操作系统(Robot Operating System, ROS)是一个应用于机器人上的操作系统,它操作方便、功能强大,特别适用于机器人这种多节点多任务的复杂场景。 因此自ROS诞生以来,受到了学术界和工业界的欢迎,如今已经广泛应用于机械臂、移动底盘、无人机、无人车等许多种类的机器人上。具体探索请参考:ROS探索总结(一)——ROS简介二、版本_ubuntu18.0ros下载

vs中如何添加ADO.NET实体数据结构_安装ado.net实体数据模型-程序员宅基地

文章浏览阅读669次,点赞2次,收藏4次。vs中如何添加ADO.NET实体数据结构_安装ado.net实体数据模型

Matlab中的括号()[]{}_matlab中中括号加数字什么意思-程序员宅基地

文章浏览阅读1.1k次。转载来自:http://blog.sina.com.cn/s/blog_618af1950100lbc3.htmlMatlab中经常会用到括号去引用某Array或者是cell的内容,但三者有什么具体区别呢?[ ] 中括号用来构建向量(Vectors)或者是矩阵(Matrices)。如[6.9 9.64 sqrt(-1)] 就是一个有三个元素的向量。[11 12 13; 21 22 _matlab中中括号加数字什么意思

Kaldi语音识别工具包简介及安装说明_kaldi sge-程序员宅基地

文章浏览阅读6.9k次,点赞4次,收藏20次。1 Kaldi简介Kaldi是一个开源的语音识别工具,整合了HTK的基本功能,同时也加入了深度神经网络的分类器(DNN)。可实现与文本无关的LVCSR系统,基于FST的训练与解码,支持多种标准的机器学习训练模型。Kaldi相关文档可参考官网:http://www.kaldi-asr.org/Kaldi内核采用c++语言编写,易于修改和扩展。有如下重要特点:Ø 有限状态_kaldi sge

随便推点

A1.计算机视觉入门_div2k_train_hr-程序员宅基地

文章浏览阅读1.4k次。单帧图像超分辨率1. 环境搭建远程环境服务器, Ubuntu 16.04, GPU 1080 Ti本地应用MobaXterm(与远程建立ssh连接,方便SFTP方式管理远程文件)Sublime(作为本地文本阅读器使用, Markdown,Code)Pycharm(可选,方便工程管理,调试)Vscode(可选,方便工程管理,调试)..._div2k_train_hr

SMS Gateway Jasmin搭建2-程序员宅基地

文章浏览阅读1.6k次。二进制部署方式安装RabbitMQ提醒安装rabbitmq repo添加RabbitMQ and Modern Erlang的repo更新yum安装依赖包和程序:开启web管理页面:安装redis官网下载redis压缩包上传服务器解压安装开启redis后台运行安装Python3检查系统是否已安装python配置python3环境变量安装jasmin-sms-gateway安装开启服务安装RabbitMQ提醒官网链接: https://www.rabbitmq.com/install-rpm.html_sms gateway

docker+k8s之docker-程序员宅基地

文章浏览阅读158次。虚拟化与容器化的区别虚拟化和容器话的性能对比namespace资源隔离docker安装yum install -y epel-releaseyum install -y yum-utilsyum-config-manager --add-repo http://mirros.aliyun.com/docker-ce/linux/centos/docker-ce.repoyum install -y doker-cesystemctl enable docker.

监听多个EditText,都不为空或满足特定条件,Button才能点击或者其他效果_监听所有值不为空-程序员宅基地

文章浏览阅读569次。时间仓促,直接写了一个内部类,先记录一下看代码 // 设置tag 区别其他的 EditText 这个不仅仅需要判空 还需要输入4位数字 (你们可以自定义你们自己的条件) msg_code_et.tag = "sms_code" /** * 自定义 TextWatcherHelper 实现 TextWatcher * * 时间仓促 思路就是这么个思路 有时间了可以封装一下 */ inner clas.._监听所有值不为空

利用MATLAB 实现高光谱影像区域截取操作_matlab截取高光谱部分图像-程序员宅基地

文章浏览阅读1.7k次。利用MATLAB 实现高光谱影像区域截取操作前言:1.相关函数说明2. Matlab 代码3. 具体效果后记欢迎学习交流:[email protected]前言:进行高光谱图像处理或者普通的二维图像处理过程中,有时候我们需要选择图像中的某个区域进行实验,因此我们渴望在高光谱影像中有一个屏幕截图的类似功能,以方便我们根据感兴趣区域实现区域的截取,下面是笔者编写的一个matlab程序,以供学者参考研究。1.相关函数说明gca: 返回当前图形窗口上的当前坐标轴对象的句柄。如果坐标轴对象不存在,_matlab截取高光谱部分图像

单片机c语言篮球比分_基于51单片机的篮球比赛计分计时器设计_毕业论文.doc-程序员宅基地

文章浏览阅读631次。PAGE \* MERGEFORMAT 4课 程 设 计 任 务 书设计题目篮球比赛计分器设计学生姓名所在院系电子信息与电气工程学院专业、年级、班设计要求:结合单片机串行口工作原理,用AT89S52设计一个篮球比赛计时计分器。能够记录整个赛程的比赛时间并可同时用数码管显示。拥有键盘接口,可通过键盘修改当前的比赛成绩(成绩修改包括加减1、2、3)。能够随时刷新甲、乙两队在整个比赛中的比赛成绩。能够..._基于单片机的篮球计分器设计毕业论文