1. 首页
  2. java数据结构

04-算法+数据解构(第04篇)空间复杂度你真的懂了吗?

在本系列第1篇《走下神坛吧!算法》中提到了:计算复杂度分为时间复杂度与空间复杂度,第3篇《KO!大O——时间复杂度》详细介绍了时间复杂度,本篇文章来讲讲空间复杂度。

空间复杂度和硬件资源开销是一回事情吗?

4-算法+数据解构(第04篇)空间复杂度你真的懂了吗?"

CPU资源开销分析:

4-算法+数据解构(第04篇)空间复杂度你真的懂了吗?"

CPU的资源的设计初衷更多的是用于提升计算性能;

对CPU资源的利用,基本原则都是“多多(占用、发挥)益善;

加之CPU的资源空间大小与内存、外存和外设比较,非常有限。

内存资源开销分析:

静态视角:程序要装进内存才能运行

动态视角:程序在运行时,动态申请内存

外存资源开销分析:

静态视角:程序本身,以二进制可执行映像形态,存放在外存上的大小

动态视角:程序在运行时,对外存的需求大小(比如,在进行大数据处理时,将中间结果暂存到外存,腾出内存空间来做计算)

4-算法+数据解构(第04篇)空间复杂度你真的懂了吗?"

发明DMA、GPU的初衷是分担CPU工作量,提升计算机系统的整体性能。

计算与存储是计算机系统的两大功用,空间复杂度体现存储指标。

不同算法实现的程序的二进制可执行映像的大小,只要不是太烂,通常来说,不会有量级上的差别。

综上所述,我们可以得到如下两个结论:

1. 空间复杂度聚焦内存与外存的开销

2. 空间复杂度聚焦动态视角

特别地,研究内存的开销,就要了解内存模型:

进一步分解,就是以下三个方面:

程序运行时,静态内存分配量(静态区)

程序运行时,动态内存分配量(堆栈、堆)

程序运行时,外存需求量

4-算法+数据解构(第04篇)空间复杂度你真的懂了吗?"

静态内存分配

这部分内存分配是用于全局变量和常量的,识别出这些变量类型,并计算出对应的大小,也就得到了该部分内存分配的需求量。具体的方法就是在源代码中找到这些变量声明、定义的地方,然后根据类型来计算大小。

动态内存分配

对于堆:对应动态分配“原语”,如 new 方法、malloc 函数等。

对于堆栈:局部变量对应这一部分,其大小呼应这部分的内存分配大小。

程序运行时的外存需求

要搞清楚程序运行时对外存的需求,首先要找到对外存的访问。

对于高级语言而言,外存是被操作系统抽象成文件来被访问的。所以找到了文件访问的“原语”,也就定位到了对外存的访问。

“文件写原语”: 如writeFile()等。作用是把内存中装载的数据放到文件中去,对文件大小的占用就反映了对外存的需求量。

“文件读原语”:如readFile()等。作用是把外存文件中的内容放到内存中去。所涉及的内容大小就反映了对外存的需求量。

从上面的分析可以看出:外存的需求量取决于访问的文件内容大小,后者又和涉及的内存大小相关。所以可以用所涉及的内存大小来表征对外存的需求量。

希望读者能够给小编留言,也可以点击[此处扫下面二维码关注微信公众号](https://www.ycbbs.vip/?p=28 "此处扫下面二维码关注微信公众号")

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:04-算法+数据解构(第04篇)空间复杂度你真的懂了吗?

    链接:https://www.javajike.com/article/2428.html

« 05-算法+数据结构(第05篇)走下神坛吧!算法
03-算法素颜(第03篇):KO!大O——时间复杂度»

相关推荐

QR code