2023-06-13  阅读(315)
原文作者:Java 极客 原文地址:https://www.javajike.com/article/2425.html

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

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

202306132114374801.png

202306132114397212.png

CPU资源开销分析:

202306132114408153.png

202306132114432824.png

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

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

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

内存资源开销分析:

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

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

外存资源开销分析:

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

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

202306132114443435.png

202306132114460146.png

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

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

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

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

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

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

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

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

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

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

程序运行时,外存需求量

202306132114474887.png

202306132114490728.png

静态内存分配

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

动态内存分配

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

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

程序运行时的外存需求

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

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

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

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

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

阅读全文
  • 点赞