• 前言
  我們在前面的排序算法的學(xué)習(xí)中了解到了,排序算法的分類,效率的比較所使用到的判斷標(biāo)準(zhǔn),就包括時間復(fù)雜度和空間復(fù)雜度,當(dāng)時因為這兩個定義還是比較難以理解的,所以決定單獨開一篇文章,記錄一下學(xué)習(xí)的過程.

• 關(guān)于時間復(fù)雜速度與空間復(fù)雜度的基本了解
  學(xué)習(xí)一項知識之前,首先要做的,就是對它要有一個基本的了解,這里我們先來看看這兩者的相關(guān)的介紹:

在計算機科學(xué)中，算法的時間復(fù)雜度（Time complexity）是一個函數(shù)，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數(shù)。時間復(fù)雜度常用大O符號表述，不包括這個函數(shù)的低階項和首項系數(shù)。使用這種方式時，時間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。

空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。

我們通過定義簡單的分析可以得出的幾條簡單的信息:

• 時間復(fù)雜度和空間復(fù)雜度都是一個函數(shù),而函數(shù)則時用來表述兩個元素之間的某一種關(guān)系的,所以時間復(fù)雜度,空間復(fù)雜度都不是指具體的某個值.

• 時間復(fù)雜度定性的描述算法的運行時間,說明時間復(fù)雜度是用來描述算法的運行速度的某種函數(shù)關(guān)系的,

• 空間復(fù)雜度是對算法需要占用的臨時空間的量度,它類似于時間復(fù)雜度,也是一個函數(shù),是關(guān)于一個問題規(guī)模為n和其消耗的內(nèi)存空間的一個函數(shù),這里我們就知道了,空間復(fù)雜度其實是類似于時間復(fù)雜度的,是相對于時間,從內(nèi)存占用方面對算法的一個描述.

• 不管時間復(fù)雜度還是空間復(fù)雜度,都是基于一個問題規(guī)模n與時間,或內(nèi)存之間的函數(shù)關(guān)系.

• 時間復(fù)雜度的理解

通過上面的簡單了解,我們再深入理解其含義,明白了其實通俗來說,就是當(dāng)一個算法輸入的值為n的時候,算法所需要消耗的時間.

例如一個算法對于任何大小為n的輸入,其運行時間為5n^{3+3n,那么它的漸近時間復(fù)雜度就是O(n}3).我們知道,其實時間復(fù)雜度表示的就是漸近時間復(fù)雜度,通常都會去除函數(shù)關(guān)系中的系數(shù)和低階項.應(yīng)為當(dāng)n趨近無窮大時,它們沒用多大的意義,而時間復(fù)雜度所考察的就是當(dāng)n趨近于無窮大時,其需要運行的時間和n的關(guān)系,所以直接就直接使用漸近時間復(fù)雜度來描述.

需要注意的時這里的n,并不是指我們所輸入的指的大小,而是我們所輸入數(shù)據(jù)的長度,通過前面的排序算法的學(xué)習(xí),我們應(yīng)該能夠很清楚的了解到了,n就是表示需要排序的序列長度,即包含多少個需要排序的數(shù)據(jù)而不是指一個數(shù)據(jù)的大小

而在我們實際生活中,每個程序的運行時間都需要實際測算才能知道的,所以我們不可能直接通過時間來計算時間復(fù)雜度,那樣不實際,那么我們通過什么來計算時間復(fù)雜度呢.我們知道一個程序的運行時間與程序的命令執(zhí)行次數(shù)時相關(guān),理論上,每條相同的執(zhí)行運行的時間時相同的,所以我們在計算某個算法的時間復(fù)雜度的時候,只需要判斷其操作單元(能夠?qū)崿F(xiàn)算法的基本程序指令集合)所需要執(zhí)行的次數(shù)即可.

• 一些常見的時間復(fù)雜度

我們都知道,函數(shù)是描述兩者這件的一種關(guān)系的,而時間復(fù)雜度就是一個函數(shù),所以我們可以將一些常見的函數(shù)關(guān)系總結(jié)起來:

2019-4-7-03.png

我們再來通過函數(shù)圖像看看幾種常見時間復(fù)雜的比較

2019-4-7-04.png

這里可以很明顯的看出各時間復(fù)雜度的優(yōu)劣關(guān)系.

對于一個算法，其時間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當(dāng)追求一個較好的時間復(fù)雜度時，可能會使空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的存儲空間；反之，當(dāng)追求一個較好的空間復(fù)雜度時，可能會使時間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長的運行時間.。算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

空間復(fù)雜度其實和時間復(fù)雜度類似,而在通常情況下,時間復(fù)雜度和空間復(fù)雜度是不能兼并的,對于遞歸算法,可以很簡短,一般效率會比較快,但空間占用多.非遞歸方法通常較為復(fù)雜,不會消耗較多的空間,但其效率一般都不會很高.

參考:
時間復(fù)雜度--維基
空間復(fù)雜度--百科

更新時間:
2019-4-7
19:30