浅识数据结构之空间复杂度

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

文章目录

一. 前言
二. 空间复杂度
三. 结语

一. 前言

了解空间复杂度相对于了解时间复杂度来说较为容易一些。
因为时间复杂度需要对程序内部或函数内部的基本语句执行次数进行判断，又时会牵扯到递归，迭代，循环等多重因素，所以计算起来相对复杂。
而空间复杂度只是代表着对一个算法在运行过程中临时占用的储存空间大小的一个量度，并且这个临时的占用大多是指除了主体函数原有的变量之外，再实现算法时额外创建的变量，或是指在递归等函数调用情况下的函数调用次数。
下面进入正式内容。

二. 空间复杂度

2.1 概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
大O渐进表示法：取影响量最大的项作为O( )的内容，且系数可以忽略。

2.2 常见的空间复杂度

O( 1 ) ：常数值的空间复杂度，一般是指调用函数次数或额外创建变量次数可以通过计数的方式的到确切的值。
O( N )：一般指递归次数为 N 或创建额外变量次数为 N 时的情形。
O( N² ) ：这种情形相对来说较为少见，但还是作为举例列明，常见的状况有创建了一个额外的二维数组，他们的额外占用空间为未知量一维数组的个数 N × 未知量一维数组中的个数 M，故空间复杂度为 N²，因 N 趋近于无穷时 N 与 M 的差值可以忽略不计，直接记为 N²。

2.3 不常见的空间复杂度，并无实际应用意义。

下面见一个经典的斐波那契数问题：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    
	if(N < 3)
	return 1;
	return Fib(N-1) + Fib(N-2);
}

当我们调用这个函数时，若所求值为第64个斐波那契数时还较为容易计算，不难看出在计算结果时，我们的函数调用了2 ^ ( 64 - 2 ) 次，故我们可以将此函数调用的空间复杂度记为O ( 2^N ) 当我们计算的数值序次偏大时，可能会消耗更多的时间，故这样的函数在实际生活中也并没有很大的应用意义。

但我们可以对其进行优化，将O ( 2^N ) 转化为 O( N )。

// 时间复杂度：O(N)
unsigned long long Fib(size_t N)
{
    
	unsigned long long f1 = 1;
	unsigned long long f2 = 1;
	unsigned long long f3 = 0;
	for (size_t i = 3; i <= N; i++)
	{
    
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
	}

	return f3;
}

此时即使计算1000位次的斐波那契数也毫无鸭梨！！

三. 结语

十分感谢您观看我的原创文章。
本文主要用于个人学习和知识分享，学习路漫漫，如有错误，感谢指正。
如需引用，注明地址。

本文链接：https://blog.csdn.net/LiU11e/article/details/138140077

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

稀疏编码的数学基础与理论分析-程序员宅基地

文章浏览阅读290次，点赞8次，收藏10次。1.背景介绍稀疏编码是一种用于处理稀疏数据的编码技术，其主要应用于信息传输、存储和处理等领域。稀疏数据是指数据中大部分元素为零或近似于零的数据，例如文本、图像、音频、视频等。稀疏编码的核心思想是将稀疏数据表示为非零元素和它们对应的位置信息，从而减少存储空间和计算复杂度。稀疏编码的研究起源于1990年代，随着大数据时代的到来，稀疏编码技术的应用范围和影响力不断扩大。目前，稀疏编码已经成为计算...

EasyGBS国标流媒体服务器GB28181国标方案安装使用文档-程序员宅基地

文章浏览阅读217次。EasyGBS - GB28181 国标方案安装使用文档下载安装包下载，正式使用需商业授权, 功能一致在线演示在线API架构图EasySIPCMSSIP 中心信令服务, 单节点, 自带一个 Redis Server, 随 EasySIPCMS 自启动, 不需要手动运行EasySIPSMSSIP 流媒体服务, 根..._easygbs-windows-2.6.0-23042316使用文档

【Web】记录巅峰极客2023 BabyURL题目复现——Jackson原生链_原生jackson 反序列化链子-程序员宅基地

文章浏览阅读1.2k次，点赞27次，收藏7次。2023巅峰极客 BabyURL之前AliyunCTF Bypassit I这题考查了这样一条链子：其实就是Jackson的原生反序列化利用今天复现的这题也是大同小异，一起来整一下。_原生jackson 反序列化链子

一文搞懂SpringCloud，详解干货，做好笔记_spring cloud-程序员宅基地

文章浏览阅读734次，点赞9次，收藏7次。微服务架构简单的说就是将单体应用进一步拆分，拆分成更小的服务，每个服务都是一个可以独立运行的项目。这么多小服务，如何管理他们？(服务治理注册中心[服务注册发现剔除])这么多小服务，他们之间如何通讯？这么多小服务，客户端怎么访问他们？(网关)这么多小服务，一旦出现问题了，应该如何自处理？(容错)这么多小服务，一旦出现问题了，应该如何排错?(链路追踪)对于上面的问题，是任何一个微服务设计者都不能绕过去的，因此大部分的微服务产品都针对每一个问题提供了相应的组件来解决它们。_spring cloud

Js实现图片点击切换与轮播-程序员宅基地

文章浏览阅读5.9k次，点赞6次，收藏20次。Js实现图片点击切换与轮播图片点击切换<!DOCTYPE html><html> <head> <meta charset="UTF-8"> <title></title> <script type="text/ja..._点击图片进行轮播图切换

tensorflow-gpu版本安装教程（过程详细）_tensorflow gpu版本安装-程序员宅基地

文章浏览阅读10w+次，点赞245次，收藏1.5k次。在开始安装前，如果你的电脑装过tensorflow，请先把他们卸载干净，包括依赖的包（tensorflow-estimator、tensorboard、tensorflow、keras-applications、keras-preprocessing），不然后续安装了tensorflow-gpu可能会出现找不到cuda的问题。cuda、cudnn。..._tensorflow gpu版本安装

随便推点

物联网时代权限滥用漏洞的攻击及防御-程序员宅基地

文章浏览阅读243次。0x00 简介权限滥用漏洞一般归类于逻辑问题，是指服务端功能开放过多或权限限制不严格，导致攻击者可以通过直接或间接调用的方式达到攻击效果。随着物联网时代的到来，这种漏洞已经屡见不鲜，各种漏洞组合利用也是千奇百怪、五花八门，这里总结漏洞是为了更好地应对和预防，如有不妥之处还请业内人士多多指教。0x01 背景2014年4月，在比特币飞涨的时代某网站曾经..._使用物联网漏洞的使用者

Visual Odometry and Depth Calculation--Epipolar Geometry--Direct Method--PnP_normalized plane coordinates-程序员宅基地

文章浏览阅读786次。A. Epipolar geometry and triangulationThe epipolar geometry mainly adopts the feature point method, such as SIFT, SURF and ORB, etc. to obtain the feature points corresponding to two frames of images. As shown in Figure 1, let the first image be and th_normalized plane coordinates

开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先抽取关系)_语义角色增强的关系抽取-程序员宅基地

文章浏览阅读708次，点赞2次，收藏3次。开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先关系再实体)一.第二代开放信息抽取系统背景第一代开放信息抽取系统(Open Information Extraction， OIE， learning-based, 自学习, 先抽取实体)通常抽取大量冗余信息，为了消除这些冗余信息，诞生了第二代开放信息抽取系统。二.第二代开放信息抽取系统历史第二代开放信息抽取系统着眼于解决第一代系统的三大问题: 大量非信息性提取（即省略关键信息的提取）、_语义角色增强的关系抽取