当前位置:首页 » 《资源分享》 » 正文

数据结构:空间复杂度_lxkeepcoding的博客

10 人参与  2021年09月13日 16:43  分类 : 《资源分享》  评论

点击全文阅读


目录

  • 前言
  • 1. 空间复杂度是个what?
  • 2. 从几个例子来理解空间复杂度的计算
    • 2.1 冒泡排序的空间复杂度
    • 2.2 斐波那契数组的空间复杂度
    • 2.3 阶乘的空间复杂度
  • 后记

前言

hello,大家好,这篇文章用来介绍空间复杂度的一些相关知识,希望对大家有所帮助,也欢迎大家批评指正。之前博主已经写过一篇介绍复杂度的文章了,主要是对时间复杂度的介绍。大家在阅读本文之前也可以先阅读一下这篇文章数据结构——优雅的复杂度。

1. 空间复杂度是个what?

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

2. 从几个例子来理解空间复杂度的计算

2.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;
}
}

在这个冒泡排序中,是接受了一个传递过来的数组的。我们在计算这个算法的空间复杂度的时候,是不考虑输入数组的,只考虑算法在运行中额外搞出来的空间
接下来我们定义了size_t 的end,int change 和size_t i。我们注意,虽然每一次循环进入,i的值会改变,但是i的空间还在那里,没有重新定义。我们要知道,时间是累计的,不可复用,而空间是不累计的,可以复用
所以,在冒泡排序中变量的个数是3,为常数,则空间复杂度为O(1)。

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 ;
}

在这个算法中,假设我们要求0~n的的斐波那契数组,我们是需要开出具有n个空间的,空间复杂度为O(N)。虽然这个算法求的不是斐波那契数组,但是在它运行的过程中,是开辟了斐波那契数组的空间的,也就是说,在运行过程中,是开辟出了n个变量空间的,虽然还定义了i等变量,但根据大O的渐进表示法,斐波那契数列的空间复杂度为O(N)。

2.3 阶乘的空间复杂度

long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

递归算法的空间复杂度通常是递归的层数。在阶乘中,每一次调用都会建立栈帧,栈帧里面存储参数和局部变量。所以在执行过程中,是建立了n个栈帧的,而每一次调用栈帧的过程中,又会使用常数个空间,根据大O的渐进表示法,空间复杂度为O(N)。

后记

好的,关于空间复杂度我们就先分享到这里了,希望对大家有所帮助。我们下期文章再见,感谢大家多多支持,你们的支持是博主进步的动力。


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/27788.html

复杂度  空间  数组  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 我的亲妹妹我当做畜生,只有儿子来救我反转剧情试读片段_[***小宝李小翠]精彩章节免费试读
  • 往梦难复温,沈淮霆宋思予在线_往梦难复温,沈淮霆宋思予在线
  • 爱意清浅随风离(简凝夕陆靳燃),爱意清浅随风离
  • 「冲喜而已,侯爷别太爱」小说免费在线阅读_侯府侯爷乐瑶主线最终章倒计时
  • 好看的往梦难复温沈淮霆宋思予_往梦难复温沈淮霆宋思予
  • 天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局(秦意宋笙)全书秦意宋笙结局_秦意宋笙+结局列表_笔趣阁(天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局)
  • (番外)+(全书)往梦难复温(沈淮霆宋思予+番外+全书)_(往梦难复温+番外+全书)免费_笔趣阁(沈淮霆宋思予)
  • 江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)列表_江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)结局篇+番外在线
  • 池雾陆砚寒结局+番外(陆砚寒池雾)列表_池雾陆砚寒结局+番外(陆砚寒池雾)池雾陆砚寒结局+番外在线
  • 沈静怡傅励行+后续+结局(傅励行沈静怡)列表_沈静怡傅励行+后续+结局(傅励行沈静怡)沈静怡傅励行+后续+结局在线
  • 非典时,我被妻子的白月光误诊遗弃在病房节选角色羁绊特辑‌_田越苏雅白月光角色专属支线试读入口
  • 往梦难复温沈淮霆宋思予_往梦难复温沈淮霆宋思予

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1