浅析时间复杂度与空间复杂度

时间复杂度

何为时间复杂度

算法的时间复杂度,是一个用于度量一个算法的运算时间的一个描述,本质是一个函数,根据这个函数能在不用具体的测试数据来测试的情况下,粗略地估计算法的执行效率,换句话讲时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势。在数据结构中,算法的时间复杂度常用大O来表述。

大O表示法

大O表示法是一种特殊的表示法,指出了算法的速度是属于哪一个数量级的。

大O表示法的数学语言描述如下:

算法的时间复杂度通常用大O符号表述,定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的“渐近时间复杂度”。

简单来说就是一个程序执行次数的估计值是在哪一个数量级的,例如八种常见排序算法的时间复杂度复杂度如下:

分析算法时间复杂度的基本方法

首先找出计算语句执行次数的数量级,接着用大O表示法来表示

例如下面这个for循环的语句要执行n次(主要是里面的i<=n要执行n次),所以它的时间复杂度是O(n)

for (i=1; i<=n; i++) 
      x++;

而下面这段代码的,第一个for循环的语句要执行n次(主要是里面的i<=n要执行n次),第二个for循环的语句要执行n次(主要是里面的j<=n要执行n次),所以它的时间复杂度是O(n^2)

for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
          x++;

特殊规则
1) 加法规则 
T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )

2) 乘法规则 
T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))

3) 常量规则
在大O表示法里面有一个特例,如果T1(n) = O(c), c是一个与n无关的任意常数,T2(n) = O ( f(n) ) 则有
        T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )

也就是说,在大O表示法中,任何非0正常数都属于同一数量级,记为O(1)。

时间复杂度分析示例

for(i=1;i<=n;i+ +)
   for(j=1j<=n;j++) {
       c[i][j]=0;
       for{k= =1:k<=n;k++)
          c[i]I[j]=c[i][j]+ a[i][k]*b[k][j]; 
}

时间复杂度:n*n*n=n3;


i=1;
while(i<=n)
    i=i*2; 

分析:

关键是要找出来执行次数x与n的关系,并表示成n的函数
若循环执行1次: i=1*2=2,
若循环执行2次: i=2*2=22(2的平方哈,下面依次)
若循环执行3次: i=2*2=23
.......
若循环执行x次: i=2x(2的x平方哈,下面依次)
又因为i要小于等于n
则2x<=n . 求出x<=log2n

所以时间复杂度为O(logN)

空间复杂度

何为空间复杂度

空间复杂度也是一个数学表达式,它是用来对算法在运行过程中临时占用存储空间大小的度量。

这里也有一个常见误区,空间复杂度并不是计算程序占用了多少字节的空间,这样做是意义不大的。所以空间复杂度计算的是变量的个数。同时间复杂度一样,空间复杂度也是采用的大O渐进表示法。

由于函数运行时所需要的栈空间(如存储参数、局部变量等)在预处理期间就已经确定好了,因此空间复杂度大多数是通过函数在运行时申请的额外空间来确定的。

空间复杂度分析示例

由于我们已经了解了时间复杂度,所以很多内容就不需要再赘述了,这里我们直接通过示例分析来理解空间复杂度的计算。


示例1

void BubbleSort(int* a, int n)
{
     assert(a);
     for (size_t end = n; end > 0; --end)
     {
         int exchange = 0;
         for (size_t i = 1; i < end; ++i)
         {
             if (a[i-1] > a[i])
         {
             Swap(&a[i-1], &a[i]);
             exchange = 1;
         }
     }
         if (exchange == 0)
             break;
     }
}

乍一看,有两个for循环,像是O(N^2)的空间复杂度,但其实不是,这里并没有使用的空间,只有线性(即常数级)的变量。所以这里的空间复杂度是O(N^2)。

也许看第一个示例还是云里雾里的,但不要在此纠结,继续看下面两个示例,会慢慢拨云见日的。


示例2

long long* Fibonacci(size_t n)
{
     if(n==0)
     return NULL;
 
     long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
     fibArray[0] = 0;
     fibArray[1] = 1;
     for (int i = 2; i <= n ; ++i)
     {
         fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
     }
     return fibArray;
}

算法中额外开辟了N个空间(指的是malloc申请的空间),所以空间复杂度为O(N)


示例3

long long Fac(size_t N)
{
     if(N == 0)
     return 1;
 
     return Fac(N-1)*N;
}

算法中递归调用了N次,开辟了N个栈帧,每个栈帧中没有额外开辟空间,即空间复杂度为O(N)。

结果分析:

要注意,这里的空间复杂度与时间复杂度的理解上有些出入。虽然主观感觉这个函数是递归调用了O(2^N)次,应该是开辟2^N块空间,但实际上并不是,因为函数在调用时并不是一直在占用,所以当一个函数执行完毕后,栈帧销毁,这块空间就释放了,下一次递归时就相当于并没有使用更多的空间。所以相当于这里的空间复杂度就是,走到最深层递归调用所占用的空间。

所以相当于空间复杂度的求法是考虑所能使用的最大空间。而时间复杂度是,只要执行一次就将这次执行的时间算进去。所以可以这样来理解 “时间是一去不复返的,用了多少就算多少;空间是可以循环利用的;能用多少就算多少”。

常见的复杂度等级比较

下表是按照时间(空间)复杂度的执行时间(执行空间)从上到下依次递增。数据结构中log如果没有特殊说明一般都是默认以2为底的。

执行次数名称级别大O记法
c(c是常量) 常数级O(1)
logN对数级O(logN)
√N根号级O(√N)
log²N对数平方级O(log²N)
N线性级O(N)
NlogN线性对数级O(NlogN)
Nlog²N线性对数平方级O(N(log²N))
平方级O(N²)
立方级O(N³)
2ⁿ指数级O(2ⁿ)

最后

由于这块内容并不难,所以这里只是浅析一波,并没有过多的赘述。如有不足,还请及时指正,接受并感谢各方的意见与批评。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/10110.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

UNIX高级编程--管道

管道 管道是 UNIX 系统 IPC 的最高老形式&#xff0c;所有的 UNIX 系统都提供此种通信机制。管道有以下两种局限性。 历史上&#xff0c;它们是半双工&#xff08;既数据只能在一个方向上流动&#xff09;。现在&#xff0c;某些系统提供全双工管道&#xff0c;但是为了最佳的…

代码随想录算法训练营第五十七天 | 647. 回文子串、516. 最长回文子序列、动态规划总结

647. 回文子串 动规五部曲 1、确定dp数组&#xff08;dp table&#xff09;以及下标的含义 在判断字符串S是否为回文时&#xff0c;如果知道 s[1]&#xff0c;s[2]&#xff0c;s[3] 这个子串是回文的&#xff0c;那么只需要比较 s[0]和s[4]这两个元素是否相同&#xff0c;如果…

Motion Planning学习笔记一:配置空间、图、图搜索、图遍历

学习高飞博士的路径规划课程所总结的学习笔记。 目录 1、配置空间&#xff08;Configuration Space, C-space&#xff09; 2、图&#xff08;Graphs&#xff09; 3、图搜索&#xff08;Graph Search Basis&#xff09; 3.1、总体框架 3.2、两种基本的图遍历算法 3.3、启…

【Python】【进阶篇】十七、Python爬虫实现实时翻译

目录十七、Python爬虫实现实时翻译17.1 JS代码slat与sign17.2 Python代码表示参数17.3 完整程序实现十七、Python爬虫实现实时翻译 YD翻译是以异步方式实现数据加载的&#xff0c;要实现数据抓取&#xff0c;其过程极其繁琐。 上一节《Python爬虫的浏览器实现抓包》&#xff…

【hello Linux】Linux开发工具

目录 1. vim&#xff1a;文本编辑器 1.1 各种模式的切换 补充&#xff1a;ctrl r命令 1.2 命令模式的操作 1.3 插入模式的操作 1.4 底行模式的操作 1.5 配置vim环境 1.6 配置亲属关系 2. gcc/g&#xff1a;编译器 2.1 预处理&#xff1a; 2.2 编译&#xff1a; 2.3 汇编&#x…

如何利用ChatGPT辅助优化刷题性能

根据土著刷题共建群里的一个小伙伴反馈&#xff0c;刷题会出现切题卡顿的情况&#xff0c;有时会出现滑不动的情况。 定位问题 为了定位切题卡顿问题的具体原因&#xff0c;测试了高低端手机&#x1f4f1;、切换2G、3G、4G低网络状态等各种影响切题的现实情况&#xff0c;经过借…

STM32F4_定时器精讲(TIM)

目录 1. 什么是定时器&#xff1f; 2. STM32定时器简介 2.1 高级控制定时器 TIM1和TIM8 2.1.1 TIM1和TIM8简介 2.1.2 时基单元 2.1.3 计数器模式 2.1.4 重复计数器 2.1.5 时钟选择 2.1.6 捕获/比较通道 2.1.7 输入捕获模式 2.1.8 其他功能 2.2 通用定时器 TIM2到TI…

Mysql 你还在一个字段一个索引吗

今天看到某系统的mysql在某时段存在thread_running线程数飙高触发告警&#xff0c;挤时间分析了该异常时间段的慢日志记录&#xff0c;并进行了sql优化 慢日志记录主要归为3个慢sql (编号1&#xff0c;2&#xff0c;3) 一、 1号sql原文 select * from feeds where topics_id &…

【MySQL数据库原理】MySQL Community安装与配置

目录 安装成功之后查看版本验证1、介绍、安装与配置数据库2、操作MySQL数据库3、MySQL数据库原理安装成功之后查看版本验证 SELECT VERSION();查看mysql版本号 1、介绍、安装与配置数据库 下载安装包:https://download.csdn.net/download/weixin_41194129/87672588 MySQL…

Visual studio C#中通过nuget安装sqlite库及C#中sliqte的用法

以前在Visual studio 的2017版中讲过如何使用sqlite&#xff0c;这里我们再次说说如何使用sqlite&#xff0c;以前Nuget使用还不是很流行很普及&#xff0c;大多数人不知道&#xff0c;但随着VS的升级&#xff0c;Nuget成为安装插件或者引用库文件标准的获取手段&#xff0c;所…

Qt Quick - TabBar

Qt Quick - TabBar使用总结一、概述二、调整选项卡三、Flickable标签三、定制化一、概述 TabBar其实就是选项卡&#xff0c;TabBar是由TabButton控件填充&#xff0c;TabBar可以与任何提供currentIndex属性的布局或容器控件一起使用&#xff0c;如StackLayout或SwipeView。Tab…

Vector - CAPL - CAN x 总线信息获取

在CAN&CANFD测试中&#xff0c;我们经常需要获取到CAN总线的负载、错误帧、过载帧、发送错误等等CAN总线上面的信息&#xff0c;这些信息如此重要&#xff0c;但是如果真的要写代码去实现也是相当不易的&#xff0c;那我们该如何去获取到的呢&#xff1f;下面我们就来一起看…

Object方法

私人博客 许小墨のBlog —— 菜鸡博客直通车 系列文章完整版&#xff0c;配图更多&#xff0c;CSDN博文图片需要手动上传&#xff0c;因此文章配图较少&#xff0c;看不懂的可以去菜鸡博客参考一下配图&#xff01; 系列文章目录 前端系列文章——传送门 JavaScript系列文章—…

柔性数组【结构体和动态内存的结合】

全文目录前言柔性数组的定义语法柔性数组的特点柔性数组的使用柔性数组的优势前言 很多人可能没有听过柔性数组这个概念&#xff0c;但是在C99中柔性数组是确实存在的。我个人感觉有点像动态内存和结构体的结合。 柔性数组的定义语法 结构中的最后一个元素允许是未知大小的数…

NumPy 秘籍中文第二版:三、掌握常用函数

原文&#xff1a;NumPy Cookbook - Second Edition 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 在本章中&#xff0c;我们将介绍许多常用函数&#xff1a; sqrt()&#xff0c;log()&#xff0c;arange()&#xff0c;astype()和sum()ceil()&#xff0c;modf()&…

《Java8实战》第1章 Java 8、9、10 以及 11 的变化

如想了解 Oracle 公司对 JDK 的最新支持情况&#xff0c;请访问https://www.oracle.com/technetwork/java/java-se-supportroadmap.html。所有的示例代码均可见于图灵社区本书主页 http://ituring.com.cn/book/2659“随书下载”处。 1.1 为什么要关心 Java 的变化 Java8做的…

[MAUI 项目实战] 手势控制音乐播放器(三): 动画

文章目录吸附动画确定位置平移动画回弹动画使用自定义缓动函数多重动画点击动画项目地址上一章节我们创建了手势容器控件PanContainer&#xff0c;它对拖拽物进行包装并响应了平移手势和点击手势。拖拽物现在虽然可以响应手势操作&#xff0c;但视觉效果较生硬&#xff0c;一个…

总结一下Redis的缓存雪崩、缓存击穿、缓存穿透

缓存是提高系统性能的一种常见手段&#xff0c;其中Redis是一种常用的高性能缓存数据库。但是在使用缓存时&#xff0c;可能会遇到一些问题&#xff0c;比如缓存击穿、缓存穿透、缓存雪崩等问题&#xff0c;本文将介绍这些问题的概念、原因以及解决方案。 缓存击穿 缓存击穿指…

SQL Server 连接查询和子查询

提示&#xff1a; 利用单表简单查询和多表高级查询技能&#xff0c;并且根据查询要求灵活使用内连接查询、外连接查询或子查询等。同时还利用内连接查询的两种格式、三种外连接查询语法格式和子查询的语法格式。 文章目录前言1.查询所有学生的学号、姓名、选修课程号和成绩方法…

Vue学习——【第四弹】

前言 上一篇文章 Vue学习——【第三弹】 中我们了解了MVVM模型&#xff0c;这篇文章接着学习Vue中的数据代理。 简单介绍 数据代理就是**一个对象(A)来代理对另一个对象(B)的属性操作(A一定要包含B)。**直接看定义大家可能觉得有些抽象&#xff0c;我们可以用代码来实现。 …
最新文章