創(chuàng)作時(shí)間：2019-03-28
作者：周林
版權(quán)所有，轉(zhuǎn)載請(qǐng)聯(lián)系作者獲取授權(quán)、并注明作者與出處
在本系列第1篇《走下神壇吧！算法》中提到了：計(jì)算復(fù)雜度分為時(shí)間復(fù)雜度與空間復(fù)雜度，第3篇《KO！大O——時(shí)間復(fù)雜度》詳細(xì)介紹了時(shí)間復(fù)雜度，本篇文章來(lái)講講空間復(fù)雜度。
空間復(fù)雜度和硬件資源開(kāi)銷(xiāo)是一回事情嗎？
CPU資源開(kāi)銷(xiāo)分析：
CPU的資源的設(shè)計(jì)初衷更多的是用于提升計(jì)算性能；
對(duì)CPU資源的利用，基本原則都是“多多（占用、發(fā)揮）益善；
加之CPU的資源空間大小與內(nèi)存、外存和外設(shè)比較，非常有限。
內(nèi)存資源開(kāi)銷(xiāo)分析：
靜態(tài)視角：程序要裝進(jìn)內(nèi)存才能運(yùn)行
動(dòng)態(tài)視角：程序在運(yùn)行時(shí)，動(dòng)態(tài)申請(qǐng)內(nèi)存
外存資源開(kāi)銷(xiāo)分析：
靜態(tài)視角：程序本身，以二進(jìn)制可執(zhí)行映像形態(tài)，存放在外存上的大小
動(dòng)態(tài)視角：程序在運(yùn)行時(shí)，對(duì)外存的需求大?。ū热?，在進(jìn)行大數(shù)據(jù)處理時(shí)，將中間結(jié)果暫存到外存，騰出內(nèi)存空間來(lái)做計(jì)算）
外設(shè)資源開(kāi)銷(xiāo)分析：
發(fā)明DMA、GPU的初衷是分擔(dān)CPU工作量，提升計(jì)算機(jī)系統(tǒng)的整體性能。
計(jì)算與存儲(chǔ)是計(jì)算機(jī)系統(tǒng)的兩大功用，空間復(fù)雜度體現(xiàn)存儲(chǔ)指標(biāo)。
不同算法實(shí)現(xiàn)的程序的二進(jìn)制可執(zhí)行映像的大小，只要不是太爛，通常來(lái)說(shuō)，不會(huì)有量級(jí)上的差別。
綜上所述，我們可以得到如下兩個(gè)結(jié)論：
1. 空間復(fù)雜度聚焦內(nèi)存與外存的開(kāi)銷(xiāo)
2. 空間復(fù)雜度聚焦動(dòng)態(tài)視角
特別地，研究?jī)?nèi)存的開(kāi)銷(xiāo)，就要了解內(nèi)存模型：
進(jìn)一步分解，就是以下三個(gè)方面：
程序運(yùn)行時(shí)，靜態(tài)內(nèi)存分配量（靜態(tài)區(qū)）
程序運(yùn)行時(shí)，動(dòng)態(tài)內(nèi)存分配量（堆棧、堆）
程序運(yùn)行時(shí)，外存需求量
靜態(tài)內(nèi)存分配
這部分內(nèi)存分配是用于全局變量和常量的，識(shí)別出這些變量類(lèi)型，并計(jì)算出對(duì)應(yīng)的大小，也就得到了該部分內(nèi)存分配的需求量。具體的方法就是在源代碼中找到這些變量聲明、定義的地方，然后根據(jù)類(lèi)型來(lái)計(jì)算大小。
動(dòng)態(tài)內(nèi)存分配
對(duì)于堆：對(duì)應(yīng)動(dòng)態(tài)分配“原語(yǔ)”，如 new方法、malloc函數(shù)等。
對(duì)于堆棧：局部變量對(duì)應(yīng)這一部分，其大小呼應(yīng)這部分的內(nèi)存分配大小。
程序運(yùn)行時(shí)的外存需求
要搞清楚程序運(yùn)行時(shí)對(duì)外存的需求，首先要找到對(duì)外存的訪問(wèn)。
對(duì)于高級(jí)語(yǔ)言而言，外存是被操作系統(tǒng)抽象成文件來(lái)被訪問(wèn)的。所以找到了文件訪問(wèn)的“原語(yǔ)”，也就定位到了對(duì)外存的訪問(wèn)。
“文件寫(xiě)原語(yǔ)”： 如writeFile()等。作用是把內(nèi)存中裝載的數(shù)據(jù)放到文件中去，對(duì)文件大小的占用就反映了對(duì)外存的需求量。
“文件讀原語(yǔ)”：如readFile()等。作用是把外存文件中的內(nèi)容放到內(nèi)存中去。所涉及的內(nèi)容大小就反映了對(duì)外存的需求量。
從上面的分析可以看出：外存的需求量取決于訪問(wèn)的文件內(nèi)容大小，后者又和涉及的內(nèi)存大小相關(guān)。所以可以用所涉及的內(nèi)存大小來(lái)表征對(duì)外存的需求量。
