【数据结构】算法的空间复杂度

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022


算法空间复杂度的定义

算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大家可能第一时间想到的都是写一个算法来判断每次输入的年份符不符合闰年的条件.但其实还有种方法是,我们可以事先建立一个有2050个元素的数组(年数比现实略多一点),然后把所有年份按下标数字对应,如果是闰年,此数组项的值设为1,否则设为0.这样,判断某年是否是闰年,就只需要查找一下对应数组项的值就可以了.这样求闰年的时间复杂度为O(1).既然空间复杂度这么好用,接下来我们就来一起学习它的基本内容吧.

上篇文章中我们一起探讨了算法的时间复杂度的相关知识,在这节我们将一起探讨算法的空间复杂度的相关知识.

先来看算法空间复杂度的定义:

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)).

其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数.

通过上节对时间复杂度的分析可知,算法的时间复杂度不是用来计算程序具体耗时的,同样的,空间复杂度也不是用来计算程序实际占用的空间的.

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用S(n)来定义.

空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐近表示法.

注意:函数运行时所需要的栈空间(存储参数,局部变量,一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时侯显示申请的额外空间来确定.

一般情况下,算法要占据的空间可以分为两部分:

  1. 算法本身要占据的空间,输入和输出,指令,常数,变量等.
  2. 算法要使用的辅助空间.

第一条大家应该很好理解,一个程序在机器上执行时,需要存储程序本身的指令,常数,变量和输入数据.

除此之外,还需要存储对数据操作的存储单元,对数据操作的存储单元即算法的辅助空间.

我们参照一个实际程序(冒泡排序函数)来理解一下这个概念:

//冒泡排序函数
void bubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换arr[j]和arr[j+1]int temp = arr[j];      //变量temp占据的空间就是辅助空间arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

如上,在冒泡排序函数中,我们需要开辟一个整形变量temp,它占据4个字节,这4个字节的空间就是冒泡排序算法在运行过程中要使用的辅助空间.

至于其他的变量i,j或是数组arr,则都属于算法本身要占据的空间,即无论使不使用冒泡排序算法程序运行都要使用的空间.这部分空间不计入算法空间复杂度的度量.


常见的空间复杂度

📌常数阶

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为O(1).

再拿上面的冒泡排序举例:

//冒泡排序函数
void bubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换arr[j]和arr[j+1]int temp = arr[j];      //变量temp每次进入if语句创建,出if语句销毁arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

可以看到,算法在运行过程中,虽然会循环很多次交换arr[j]和arr[j+1]的操作,但在这过程中创建的变量temp每次都是进入if语句后被创建,出if语句后被销毁,因此即便创建temp的语句运行的次数随n的增大在不断变多,但其本质上用的都是同一块空间,不论n大小如何变化,temp占用的空间大小都不会变化,因此冒泡排序的空间复杂度为O(1).


📌线性阶

如果算法执行所需要的临时空间随着某个变量n的大小呈线性变化,即此算法空间复杂度为一个线性阶,可表示为O(n).

假设我们现在要求出从0开始的n个素数,将它们存储在数组arr中,代码如下:

int main()
{int i, j,k, flag;int n;       int arr[n] = { 0 };     //仅作示例演示,正式编程时变量不能作为数组长度for (i = 0; k < n; i++){flag = 1;for (j = 2; j < i; j++){if (i % j == 0){flag = 0;break;}}if (flag == 1){arr[k] = i;k++;}}return 0;
}

在这个程序中我们就需要开辟长度为n的数组来存放我们求得的n个素数.显而易见,开辟的数组长度n是随着问题规模的n增长而增长的,且呈线性相关,因此该程序的空间复杂度为O(n).


常见的时间复杂度及其耗费空间排序

常见的空间复杂度
执行次数函数非正式术语
5201314O(1)常数阶
2n+3O(n)线性阶
3n^2+2n+1O(n^2)平方阶
5\log_{2}n+20O(logn)对数阶
2n+3n\log_{2}n+19O(nlogn)nlogn阶
6n^3+2n^2+3n+4O(n^3)立方阶
2^nO(2^n)指数阶

常用的空间复杂度所耗费的空间从小到大依次是:

O(1)<O(logn)<O(n)<O(nlogn)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})

 


结语

当我们搞清楚算法的空间复杂度后,数据结构算法篇的内容就结束了,接下来我们将开启数据结构新的章节——线性表,在新章节中我们将一起学习如何实现顺序表,单链表,双链表,循环链表等相关知识.希望这些内容能对大家有所帮助,一起学习,一起进步!

相关文章推荐

【数据结构】什么是数据结构?

【数据结构】什么是算法?

【数据结构】算法效率的度量方法

【数据结构】算法的时间复杂度

【C语言】冒泡排序

【数据结构】什么是线性表?

......



数据结构算法篇思维导图:

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

github创建个人网页登录后404无法显示的问题

1.首先必须要有内容&#xff0c;默认是会找index.html文件&#xff0c;找不到该文件会找readme.md文件&#xff0c;也就是说最简单的方法是&#xff0c;创建了与用户名同名的repository后username.github.io后&#xff0c;添加一个readme.md文件&#xff0c;得在readme里打点字…

【算法-动态规划】最长上升子序列-力扣 300

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…

设计模式-相关内容

文章目录 一、设计模式概述二、UML图1.类的表示方法2.类与类之间关系的表示方法(1)关联关系(2)聚合关系(3)组合关系(4)依赖关系(5)继承关系(6)实现关系 三、软件设计原则1.开闭原则2.里氏代换原则3.依赖倒转原则4.接口隔离原则5.合成复用原则6.迪米特法则 一、设计模式概述 创…

驾驶数字未来:汽车业界数字孪生技术的崭新前景

随着数字化时代的到来&#xff0c;汽车行业正经历着前所未有的变革。数字孪生技术&#xff0c;作为一种前沿的数字化工具&#xff0c;正在为汽车行业带来革命性的影响&#xff0c;不仅改变着汽车制造和维护的方式&#xff0c;也为消费者带来了前所未有的体验。让我们一起探讨&a…

[sqoop]hive导入mysql,其中mysql的列存在默认值列

一、思路 直接在hive表中去掉有默认值的了列&#xff0c;在sqoop导入时,指定非默认值列即可&#xff0c; 二、具体 mysql的表 hive的表 create table dwd.dwd_hk_rcp_literature(id string,literature_no string,authors string,article_title string,source_title string…

OLED透明拼接屏:福州鼓山风景区:徜徉于城市壮丽之

福州是中国福建省的省会城市&#xff0c;历史悠久&#xff0c;文化底蕴深厚。 该城市曾是唐宋时期的重要港口城市&#xff0c;也是丝绸之路海上丝绸之路的起点之一。 福州以其独特的地理位置和丰富的历史遗产而闻名于世。 福州拥有众多的历史景点&#xff0c;其中最著名的是…

MySQL为什么用b+树

索引是一种数据结构&#xff0c;用于帮助我们在大量数据中快速定位到我们想要查找的数据。 索引最形象的比喻就是图书的目录了。注意这里的大量&#xff0c;数据量大了索引才显得有意义&#xff0c;如果我想要在[1,2,3,4]中找到4这个数据&#xff0c;直接对全数据检索也很快&am…

动态盘转换为基本盘

问题描述 不小心将磁盘0&#xff08;C和D是基本盘&#xff0c;蓝颜色&#xff09;改成了动态盘&#xff08;C和D是动态盘&#xff0c;橘黄色&#xff09;&#xff1f;如何修改回来呢&#xff1f; 解决方案&#xff1a; 使用DiskGenius将动态磁盘转换为基本磁盘 操作之前一定…

风电光伏混合储能功率小波包分解、平抑前后波动性分析、容量配置、频谱分析、并网功率波动分析(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【java|golang】多字段排序以及排序规则

奖励最顶尖的 K 名学生 给你两个字符串数组 positive_feedback 和 negative_feedback &#xff0c;分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。 一开始&#xff0c;每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分&#xff0c;每个负面的词…

智慧空开让用电更安全、管理更智能——电脑APP远程控制开合闸

安科瑞 崔丽洁 01 什么是低压断路器&#xff1f;低压断路器的定义是&#xff1a;能够接通、承载及分断正常电路条件下的电流&#xff0c;也能在规定的非正常电路条件&#xff08;过载、短路、特别是短路&#xff09;下接通、承载一定时间和分断电流的开关电器。 断路器的分类&…

拼多多商品品牌数据接口,拼多多商品详情数据接口,拼多多优惠券数据接口,拼多多API接口

拼多多商品品牌数据采集方法如下&#xff1a; 手动数据采集。直接在拼多多平台上搜索并手动复制商品数据&#xff0c;适合采集小批量的商品数据&#xff0c;但不适用于大规模数据采集。手动采集需要手动输入搜索词&#xff0c;进行筛选后再复制所需的数据&#xff0c;该方法需…

白银做期货还是做现货?

现货白银和期货白银都是保证金交易品种&#xff0c;都具有一定的资金杠杆&#xff0c;新手投资者在它们之间进行选择的时候&#xff0c;可能会遇到一定的困难&#xff0c;但是只要投资者真正了解过它们的区别&#xff0c;在选择时思路就会更加清晰&#xff0c;能够根据自己的实…

Stable Diffusion XL搭建

本文参考&#xff1a;Stable Diffusion XL1.0正式发布了&#xff0c;赶紧来尝鲜吧-云海天教程 Stable Diffision最新模型SDXL 1.0使用全教程 - 知乎 1、SDXL与SD的区别 &#xff08;1&#xff09;分辨率得到了提升 原先使用SD生成图片&#xff0c;一般都是生成512*512&…

VMWare配置桥接

一、设置网络模式 二、编辑网卡配置 ip配置的子网掩码和默认网关保持和宿主机一致&#xff0c;ip局域网内不冲突。 # cd /etc/sysconfig/network-scriptslsvim ifcfg-ens160 TYPEEthernet PROXY_METHODnone BROWSER_ONLYno BOOTPROTOnone DEFROUTEyes IPV4_FAILURE_FATALno IP…

hive 之select 中文乱码

此处的中文乱码和mysql的库表 编码 latin utf 无关。 直接上案例。 有时候我们需要自定义一列&#xff0c;有时是汉字有时是字母&#xff0c;结果遇到这种情况了。 说实话看到这真是糟心。这谁受得了。 单独select 没有任何问题。 这是怎么回事呢&#xff1f; 经过一番检查&…

C++11新特性(lambda,可变参数模板,包装器,bind)

lambda表达式是什么&#xff1f;包装器又是什么&#xff1f;有什么作用&#xff1f;莫急&#xff0c;此篇文章将详细带你探讨它们的作用。很多同学在学习时害怕这些东西&#xff0c;其实都是方便使用的工具&#xff0c;很多情况下我们学这些新的东西觉得麻烦&#xff0c;累赘&a…

服务器数据恢复-DS5300存储raid5硬盘出现坏道离线的数据恢复案例

服务器数据恢复环境&#xff1a; 某单位一台DS5300存储&#xff0c;1个主机4个扩展柜&#xff0c;组建了2组RAID5&#xff08;一组27块硬盘&#xff0c;一组23块盘&#xff09;。27块盘的那组RAID5阵列存放Oracle数据库文件&#xff0c;存储系统一共分了11个卷。 服务器故障&a…

linux C++ vscode连接mysql

1.linux使用Ubuntu 2.Ubuntu安装vscode 2.1 安装的是snap版本,直接打开命令行执行 sudo snap install --classic code 3.vscode配置C 3.1 直接在扩展中搜索C安装即可 我安装了C, Chinese, code runner, 安装都是同理 4.安装mysql sudo apt update sudo apt install mysql-…

MySQL 安装+启动+报错的解决方案

目录 一、安装准备 1.1 下载 1.2 版本说明 二、安装步骤 2.1 解压缩 2.2 配置环境变量 2.3 配置文件 2.4 安装 2.5 启动/停止服务 三、使用说明 3.1 用户名密码登录 3.1 设置用户名密码 四、卸载步骤 4.1 卸载服务 五、安装问题 六、启动问题 6.1 提示【服务无…