計(jì)算機(jī)程序設(shè)計(jì)的空間時(shí)間轉(zhuǎn)換優(yōu)化

第第頁計(jì)算機(jī)程序設(shè)計(jì)的空間時(shí)間轉(zhuǎn)換優(yōu)化在計(jì)算機(jī)程序設(shè)計(jì)中，兩個(gè)最重要的指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度是指程序運(yùn)行時(shí)所需要的時(shí)間，簡稱時(shí)間。由于計(jì)算機(jī)CPU執(zhí)行指令時(shí)是由CPU內(nèi)部的計(jì)算器單挑指令依次執(zhí)行（多核計(jì)算機(jī)除外），因此時(shí)間復(fù)雜度可以簡單的由指令的執(zhí)行次數(shù)來決定，簡稱時(shí)間；通常我們通過輸入數(shù)據(jù)的規(guī)模來表示，例如程序輸入的規(guī)模是n個(gè)數(shù)據(jù)，n的線性倍數(shù)的時(shí)間復(fù)雜度：執(zhí)行1n次運(yùn)算，或者執(zhí)行2n運(yùn)算可以統(tǒng)稱為O（n），而（n-1）*n次運(yùn)算，n*n次運(yùn)算則可以統(tǒng)稱為O（n2）。空間復(fù)雜度是指在程序執(zhí)行時(shí)，所需要的額外的臨時(shí)存儲(chǔ)空間來存儲(chǔ)臨時(shí)的運(yùn)算結(jié)果，空間復(fù)雜度的衡量可以通過類似時(shí)間復(fù)雜度衡量的規(guī)則，這里不再贅述。

【關(guān)鍵詞】轉(zhuǎn)換優(yōu)化計(jì)算機(jī)程序設(shè)計(jì)

通常在設(shè)計(jì)程序時(shí)，要考慮時(shí)間和空間的平衡以追求合理的時(shí)間和空間。通過合理的數(shù)據(jù)存儲(chǔ)以及操作，空間復(fù)雜度可以有效地降低時(shí)間復(fù)雜度。單純的追求時(shí)間或者空間之一，則有可能造成無法接受的錯(cuò)誤。例如如果時(shí)間復(fù)雜度過于高，則程序的時(shí)間響應(yīng)速度會(huì)非常慢，當(dāng)輸入問題的數(shù)據(jù)量達(dá)到一定規(guī)模，程序可能會(huì)無限長的運(yùn)行下去。同樣，由于計(jì)算機(jī)的內(nèi)存空間是有限的，當(dāng)空間要求過大時(shí)，程序可能會(huì)用光所有的內(nèi)存空間，這樣程序會(huì)因?yàn)榭臻g不足無法繼續(xù)運(yùn)行。一下我們以一個(gè)簡單的實(shí)際問題來表述時(shí)間和空間的轉(zhuǎn)化，以及平衡的復(fù)雜度安排的重要性。

假設(shè)我們有如下問題：輸入n個(gè)整數(shù)（n>1），返回這n個(gè)數(shù)據(jù)是否有重復(fù)。

1首先我們考慮最簡單不用臨時(shí)存儲(chǔ)的情況，程序數(shù)據(jù)如下：

對輸入的每一個(gè)數(shù)據(jù)依次執(zhí)行：

查看每一個(gè)其他的數(shù)字，對當(dāng)前數(shù)據(jù)進(jìn)行比較：

如果相同，則返回程序結(jié)果有重復(fù)。

如果不同，則對下一個(gè)數(shù)字進(jìn)行分析。

我們對如上的設(shè)計(jì)進(jìn)行分析，在最快的情況，前兩個(gè)數(shù)就有重復(fù)，那么一次比較就知道有重復(fù)。在最壞的情況下，?即n個(gè)數(shù)字沒有重復(fù)，對每一個(gè)數(shù)字，我們都要進(jìn)行n（實(shí)際上是n-1次，我們用n來近似）次比較。所以當(dāng)不用臨時(shí)存儲(chǔ)總的運(yùn)算量是n*n次比較。在實(shí)際問題中，由于我們不知道問題的情況，無法預(yù)測有沒有重復(fù)或者在哪里重復(fù)，所以我們要一直用最壞的情況進(jìn)行分析。在此問題中時(shí)間復(fù)雜度是n*n，沒有用到輔助空間。

2程序優(yōu)化

此程序可以進(jìn)行優(yōu)化，對每個(gè)數(shù)據(jù)和其他數(shù)據(jù)比較時(shí)，不用和該數(shù)之前的數(shù)據(jù)比較，因?yàn)樵摯伪容^已經(jīng)被執(zhí)行過了。比如：對1，2，3，這個(gè)問題進(jìn)行比較，首先我們比較1與2，1與3，然后我們開始對第二個(gè)數(shù)分析，這時(shí)不用繼續(xù)比較2與1，因?yàn)?與2已經(jīng)執(zhí)行過，只需要比較2與3程序修改

所以修改程序如下：

對輸入的每一個(gè)數(shù)據(jù)依次執(zhí)行：

查看每一個(gè)在此數(shù)據(jù)之后的數(shù)字，對當(dāng)前數(shù)據(jù)進(jìn)行比較：

如果相同，則返回程序結(jié)果有重復(fù)。

如果不同，則對下一個(gè)數(shù)字進(jìn)行分析。

我們對如上的設(shè)計(jì)進(jìn)行分析，在最壞的情況下，即n個(gè)數(shù)字沒有重復(fù)，對第一個(gè)數(shù)字，我們要進(jìn)行n（實(shí)際上是n-1次，我們用n來近似）次比較，第二個(gè)數(shù)字n-1次比較，第三個(gè)數(shù)字n-2次比較……所以當(dāng)不用臨時(shí)存儲(chǔ)總的運(yùn)算量是n（n+1）/2次比較，沒有用到輔助空間。

最后我們用一個(gè)帶有臨時(shí)存儲(chǔ)空間的算法：我們把每一個(gè)數(shù)據(jù)存到臨時(shí)空間里（注：此臨時(shí)空間能提供非?？斓拇鎯?chǔ)和查看操作，忽略存儲(chǔ)和查看的操作時(shí)間），查看當(dāng)前數(shù)據(jù)是否已經(jīng)在存儲(chǔ)空間內(nèi)，如果有，則返回是，如果沒有，則繼續(xù)下一個(gè)數(shù)據(jù)：

3創(chuàng)建一個(gè)臨時(shí)的空存儲(chǔ)空間

對輸入的每一個(gè)數(shù)據(jù)依次執(zhí)行：

查看存儲(chǔ)空間是否有這個(gè)數(shù)據(jù)

如果有，則返回程序結(jié)果有重復(fù)。

如果沒有，則對下一個(gè)數(shù)字進(jìn)行分析，并且將當(dāng)前數(shù)據(jù)儲(chǔ)存到存儲(chǔ)空間。

我們對如上的設(shè)計(jì)進(jìn)行分析，在最壞的情況下，即n個(gè)數(shù)字沒有重復(fù)，對每一個(gè)數(shù)字，我們都要進(jìn)行1次查看，所以當(dāng)使用臨時(shí)存儲(chǔ)總的運(yùn)算量是n，額外的輔助空間大小也為n。

到此，我們的程序設(shè)計(jì)完畢，為什么利用輔助存儲(chǔ)降低時(shí)間復(fù)雜度重要呢？我們進(jìn)行如下分析：

假設(shè)有計(jì)算機(jī)A，每微秒執(zhí)行一次指令，那么此計(jì)算機(jī)每秒鐘可以執(zhí)行106次指令。假設(shè)程序的輸入為10個(gè)數(shù)，那么三個(gè)程序所需要的時(shí)間依次為T1=10*10/106=0.0001秒，T2=（10*11/2）/106=0.000055秒，T3=10/106=0.00001。在輸入規(guī)模不大時(shí)候，相差不大。如果輸入為10000個(gè)數(shù)，三個(gè)程序所需要的時(shí)間為T1=104*104/106=100秒，T2=（10000*10001/2）/106=0.000055=50.005秒，而T3=10000/106=0.01秒?？梢杂?jì)算，當(dāng)輸入為一百萬個(gè)數(shù)字時(shí)，第一個(gè)程序需要運(yùn)行27小時(shí)，而第三個(gè)程序只需要一秒鐘！

我們換另外一種分析方法，如果我們有另外一條比較快的電腦B，每秒鐘可以進(jìn)行109運(yùn)算，則B電腦比A電腦快1000倍！我們用慢電腦A處理有額外空間的程序，快電腦B處理沒有額外存儲(chǔ)的第一個(gè)程序，那么當(dāng)輸入為10萬個(gè)整數(shù)時(shí)，A電腦需要0.1秒處理該問題，B電腦需要10秒處理該問題！A電腦在本身速度比B小1000倍的時(shí)候，計(jì)算速度反而可以可以比B快100倍?？梢娨粋€(gè)優(yōu)化的算法可以迅速的提高電腦響應(yīng)速度，而不需要花費(fèi)太多成本在提高電腦本身的速率上面。

可以看出，當(dāng)問題規(guī)模變大時(shí)，額外的輔助存儲(chǔ)可以大規(guī)模的降低時(shí)間復(fù)雜度。有些讀者可能會(huì)質(zhì)疑額外的存儲(chǔ)可能會(huì)很大，但是以這個(gè)問題為例，最差的情況下需要10000個(gè)整數(shù)的存儲(chǔ)空間。一個(gè)整數(shù)占4B，10000個(gè)整數(shù)只需要40KB的存儲(chǔ)空間，小于一張小圖片的大小，幾乎相當(dāng)于一個(gè)純文本文件的大小。由此可見適當(dāng)?shù)睦每臻g存儲(chǔ)可以有效的減少額外存儲(chǔ)。