- 前言
我們?cè)谇懊娴呐判蛩惴ǖ膶W(xué)習(xí)中了解到了,排序算法的分類,效率的比較所使用到的判斷標(biāo)準(zhǔn),就包括時(shí)間復(fù)雜度和空間復(fù)雜度,當(dāng)時(shí)因?yàn)檫@兩個(gè)定義還是比較難以理解的,所以決定單獨(dú)開一篇文章,記錄一下學(xué)習(xí)的過程.
-
關(guān)于時(shí)間復(fù)雜速度與空間復(fù)雜度的基本了解
學(xué)習(xí)一項(xiàng)知識(shí)之前,首先要做的,就是對(duì)它要有一個(gè)基本的了解,這里我們先來看看這兩者的相關(guān)的介紹:
在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度（Time complexity）是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時(shí)的情況。
空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))。類似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。
我們通過定義簡(jiǎn)單的分析可以得出的幾條簡(jiǎn)單的信息:
時(shí)間復(fù)雜度和空間復(fù)雜度都是一個(gè)函數(shù),而函數(shù)則時(shí)用來表述兩個(gè)元素之間的某一種關(guān)系的,所以時(shí)間復(fù)雜度,空間復(fù)雜度都不是指具體的某個(gè)值.
時(shí)間復(fù)雜度定性的描述算法的運(yùn)行時(shí)間,說明時(shí)間復(fù)雜度是用來描述算法的運(yùn)行速度的某種函數(shù)關(guān)系的,
空間復(fù)雜度是對(duì)算法需要占用的臨時(shí)空間的量度,它類似于時(shí)間復(fù)雜度,也是一個(gè)函數(shù),是關(guān)于一個(gè)問題規(guī)模為n和其消耗的內(nèi)存空間的一個(gè)函數(shù),這里我們就知道了,空間復(fù)雜度其實(shí)是類似于時(shí)間復(fù)雜度的,是相對(duì)于時(shí)間,從內(nèi)存占用方面對(duì)算法的一個(gè)描述.
不管時(shí)間復(fù)雜度還是空間復(fù)雜度,都是基于一個(gè)問題規(guī)模n與時(shí)間,或內(nèi)存之間的函數(shù)關(guān)系.
- 時(shí)間復(fù)雜度的理解
通過上面的簡(jiǎn)單了解,我們?cè)偕钊肜斫馄浜x,明白了其實(shí)通俗來說,就是當(dāng)一個(gè)算法輸入的值為n的時(shí)候,算法所需要消耗的時(shí)間.
例如一個(gè)算法對(duì)于任何大小為n的輸入,其運(yùn)行時(shí)間為5n3+3n,那么它的漸近時(shí)間復(fù)雜度就是O(n3).我們知道,其實(shí)時(shí)間復(fù)雜度表示的就是漸近時(shí)間復(fù)雜度,通常都會(huì)去除函數(shù)關(guān)系中的系數(shù)和低階項(xiàng).應(yīng)為當(dāng)n趨近無窮大時(shí),它們沒用多大的意義,而時(shí)間復(fù)雜度所考察的就是當(dāng)n趨近于無窮大時(shí),其需要運(yùn)行的時(shí)間和n的關(guān)系,所以直接就直接使用漸近時(shí)間復(fù)雜度來描述.
需要注意的時(shí)這里的n,并不是指我們所輸入的指的大小,而是我們所輸入數(shù)據(jù)的長(zhǎng)度,通過前面的排序算法的學(xué)習(xí),我們應(yīng)該能夠很清楚的了解到了,n就是表示需要排序的序列長(zhǎng)度,即包含多少個(gè)需要排序的數(shù)據(jù)而不是指一個(gè)數(shù)據(jù)的大小
而在我們實(shí)際生活中,每個(gè)程序的運(yùn)行時(shí)間都需要實(shí)際測(cè)算才能知道的,所以我們不可能直接通過時(shí)間來計(jì)算時(shí)間復(fù)雜度,那樣不實(shí)際,那么我們通過什么來計(jì)算時(shí)間復(fù)雜度呢.我們知道一個(gè)程序的運(yùn)行時(shí)間與程序的命令執(zhí)行次數(shù)時(shí)相關(guān),理論上,每條相同的執(zhí)行運(yùn)行的時(shí)間時(shí)相同的,所以我們?cè)谟?jì)算某個(gè)算法的時(shí)間復(fù)雜度的時(shí)候,只需要判斷其操作單元(能夠?qū)崿F(xiàn)算法的基本程序指令集合)所需要執(zhí)行的次數(shù)即可.
- 一些常見的時(shí)間復(fù)雜度
我們都知道,函數(shù)是描述兩者這件的一種關(guān)系的,而時(shí)間復(fù)雜度就是一個(gè)函數(shù),所以我們可以將一些常見的函數(shù)關(guān)系總結(jié)起來:
我們?cè)賮硗ㄟ^函數(shù)圖像看看幾種常見時(shí)間復(fù)雜的比較
這里可以很明顯的看出各時(shí)間復(fù)雜度的優(yōu)劣關(guān)系.
對(duì)于一個(gè)算法，其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當(dāng)追求一個(gè)較好的時(shí)間復(fù)雜度時(shí)，可能會(huì)使空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的存儲(chǔ)空間；反之，當(dāng)追求一個(gè)較好的空間復(fù)雜度時(shí)，可能會(huì)使時(shí)間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長(zhǎng)的運(yùn)行時(shí)間.。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。
空間復(fù)雜度其實(shí)和時(shí)間復(fù)雜度類似,而在通常情況下,時(shí)間復(fù)雜度和空間復(fù)雜度是不能兼并的,對(duì)于遞歸算法,可以很簡(jiǎn)短,一般效率會(huì)比較快,但空間占用多.非遞歸方法通常較為復(fù)雜,不會(huì)消耗較多的空間,但其效率一般都不會(huì)很高.
參考:
時(shí)間復(fù)雜度--維基
空間復(fù)雜度--百科
更新時(shí)間:
2019-4-7
19:30
