這是數(shù)據(jù)結(jié)構(gòu)系列文章的第一篇，這是文章的列表。
注：想要學(xué)好數(shù)據(jù)結(jié)構(gòu)，掌握至少一門語言是必需的，這樣才能將學(xué)到的數(shù)據(jù)結(jié)構(gòu)知識加以鞏固。

文章目錄

1. 語言以及代碼書寫規(guī)范
2. 時間復(fù)雜度和空間復(fù)雜度分析
3. 數(shù)據(jù)結(jié)構(gòu)與算法中的一些概念

1. 語言以及代碼書寫規(guī)范

1. 語言其實無所謂，重點在于數(shù)據(jù)結(jié)構(gòu)的知識。不同語言實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)算法，其實大同小異。在教科書中，常用的語言有C/C++ 和 java兩種。

2. 這兩種語言在在數(shù)據(jù)結(jié)構(gòu)與算法上，轉(zhuǎn)化起來其實很簡單，所以以后的文章，可能會用到這兩種語言。
3. 代碼書寫規(guī)范：
   • 程序中用到的某些常量或者調(diào)用的函數(shù)等可以用加注釋的方式，省略其定義。
   • include語句可不寫
   • 測試代碼可不寫
   • 數(shù)據(jù)類型上，int， char及其數(shù)組類型，指針類型即可覆蓋大部分

2. 時間復(fù)雜度和空間復(fù)雜度分析

• 其實對于一些簡單的程序，時間復(fù)雜度和空間復(fù)雜度是比較簡單的，但是也有難的地方，特別是算法中涉及到遞歸等比較高級的特性時。時間復(fù)雜度的考察較多。

• 在考研中，時間復(fù)雜度的考察一般是考察排序算法中的復(fù)雜度，這只需要簡單記憶或者理解記憶即可。當(dāng)然，也不僅僅是這樣的，也會給你一段程序，要你分析其復(fù)雜度，這就需要你有一定的分析能力了。

(1) 時間復(fù)雜度

1) 常用的時間復(fù)雜度比較關(guān)系（需要牢記）：

時間復(fù)雜度的比較關(guān)系.png

2) 實例分析

• 分析時間復(fù)雜度其實就是分析算法每個指令執(zhí)行的次數(shù)。而一般一行一行的代碼其實其執(zhí)行次數(shù)為常數(shù)，一般不考慮，所以一般要分析的地方在循環(huán)、遞歸等地方。

• 計算出執(zhí)行次數(shù)后，一般是一個n的表達式，只需要提取式子中隨著n的變化而變化最快的那個部分，一般是在(1)中比較關(guān)系里的那些。

實例1：純循環(huán)的情況

這種情況只需要簡單計算循環(huán)內(nèi)的指令執(zhí)行次數(shù)就行了。

實例1.png

以上代碼第一層是n次循環(huán)，第二層是n - (i + 1) + 1 = n - i次循環(huán)，而i是從0開始到n - 1, 所以總的次數(shù)應(yīng)該是：

i = 0 時， target 運行 n - 1 次
i = 1 時， target 運行 n - 2 次
...
i = n - 1 時，target 運行 0 次
所以總共次數(shù) = (n - 1) + (n - 2) + (n - 3) + ... + 0 
總共有n項，根據(jù)等差數(shù)列求和：sum = ((n-1) + 0) * n/ 2 = n(n-1) / 2

實例2：循環(huán)次數(shù)依賴循環(huán)內(nèi)數(shù)據(jù)變化的情況

有些題目中，循環(huán)的次數(shù)要依賴循環(huán)內(nèi)部變量的變化情況而定。

image.png

上述代碼只有一個while循環(huán)，但是循環(huán)次數(shù)需要通過i和s計算, 1,2兩條指令會影響循環(huán)的跳出。并不是簡單的自增1。

初始：i = 0, s = 0
i = 1, s += i = 1 // 1次
i = 2, s += i = 1 + 2 = 3 // 2次
i = 3, s += i = 1 + 2 + 3  = 6  // 3次
...
i = m, s += m = 1 + 2 + 3 + ... + m = m(m+1)/2   // m次

假設(shè)循環(huán)m次結(jié)束，那么 s = m(m+1)/2  >= n
換一種表示方式：m(m+1)/2 + k = n， k為一個常數(shù)
則有：m*m + m + 2k -2n = 0

image.png

image.png

實例3：遞歸的情況

image.png

遞歸的情況分析會比較難，但是也有一般的套路。上面的代碼是歸并排序的關(guān)鍵代碼。merge函數(shù)的復(fù)雜度為O(n)。

-> 設(shè)因為merge的復(fù)雜度為O(n)，所以可以假設(shè)其操作次數(shù)為cn，再假設(shè)mergesort的操作次數(shù)為f(n).
-> 實例中的規(guī)模為：j - i + 1，若調(diào)用mergesort(1, n)， 那么規(guī)模就是n。
-> 一個規(guī)模為n的mergesort指令 = 兩個規(guī)模為n/2的mergesort指令 + cn
即：

image.png

假設(shè)最后的問題

(2) 空間復(fù)雜度

3. 數(shù)據(jù)結(jié)構(gòu)與算法中的一些概念