課程：《數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號岩馍？》 總結(jié)
數(shù)組，是一種線性表數(shù)據(jù)結(jié)構(gòu)抖韩。它用一組連續(xù)的內(nèi)存空間蛀恩，來存儲一組具有相同類型的數(shù)據(jù)。作為一種最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)茂浮，每一種編程語言中都存在它的身影双谆。數(shù)組有一個“殺手锏”：隨機訪問。它按下標(biāo)隨機訪問的時間復(fù)雜度為 O(1)席揽。
1. 數(shù)組如何實現(xiàn)隨機訪問
在計算機中顽馋，想要訪問一個數(shù)據(jù)，必須知道這個數(shù)據(jù)存放空間的存儲地址幌羞。如果用一個 int a[10] 的數(shù)組舉例寸谜，int 類型為 4 個字節(jié)，并且數(shù)組具有連續(xù)空間和相同類型的特寫可以得到下圖存儲：
假設(shè)數(shù)組 a[10] 的首地址是1000属桦，即熊痴，base_address = 1000，那么數(shù)組每一個存儲單元的地址和下表k的關(guān)系如下：
a[k]_address = base_address + k * type_size
其中：type_size 為數(shù)組中每個元素的大小地啰，在這里就是int類型的大小愁拭，type_size = 4讲逛。
根據(jù)上述尋址公式亏吝，可以得到：a[0] 的地址=1000 + 0 * 4 = 1000；a[1] 的地址=1000 + 1 * 4 = 1004盏混； a[2] 的地址=1000 + 2 * 4 = 1008蔚鸥，以此類推，都可以通過 下標(biāo) 找到每一個元素的地址進(jìn)行訪問许赃。
2. 數(shù)組的下標(biāo)為何從0開始
關(guān)于這個問題止喷，大家不必深究，了解幾種可信度較高的說法即可：
追求極致的效率
當(dāng)數(shù)組的下標(biāo)從不是0的數(shù)字開始時混聊，比如從1開始弹谁，那么前面的尋址公式，就會變?yōu)椋?/p>
a[k]_address = base_address + (k - 1) * type_size
不難看出，每做一次尋址预愤，都會多做一次減法運算沟于，數(shù)組作為非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)植康，通過下標(biāo)隨機訪問數(shù)組元素又是其非晨跆基礎(chǔ)的編程操作，為了將效率優(yōu)化到極致销睁，所以選用了下標(biāo)從0開始供璧。
歷史原因
C 語言設(shè)計者用 0 開始計數(shù)數(shù)組下標(biāo)，之后的很多高級語言都效仿了 C 語言冻记，或者說睡毒，為了在一定程度上減少 C 語言程序員學(xué)習(xí) 其它高級語言的學(xué)習(xí)成本，因此繼續(xù)沿用了從 0 開始計數(shù)的習(xí)慣冗栗。
3. 數(shù)組的插入和刪除復(fù)雜度
數(shù)組雖然有隨機訪問這樣的“殺手锏”吕嘀，但是，數(shù)組的特性導(dǎo)致了插入贞瞒、刪除這兩個操作比較低效偶房。
-
插入操作
假設(shè)數(shù)組長度為 n，如果在數(shù)組末尾插入元素军浆，那么此時數(shù)組無需移動其它元素棕洋，即，最好時間復(fù)雜度為 O(1) 乒融。如果在數(shù)組開頭插入元素掰盘，為了保證數(shù)組的空間連續(xù)性，需要將數(shù)組的 n 個元素都向后移動一個位置赞季，即愧捕，最壞的時間復(fù)雜度為 O(n) 。如果在數(shù)組的第 k 個位置插入元素申钩，需要將數(shù)組第 k~n 個元素向后移動一個位置次绘，插入位置的情況總共有 n+1 種，假設(shè)在每個位置插入的概率是一樣的撒遣，那么在第 k 個位置插入元素的平均時間復(fù)雜度就為：
T(n) = O(0) x+ O(1) x
) = O(
) = O(n)
-
刪除操作
假設(shè)數(shù)組長度為 n邮偎，如果刪除數(shù)組末尾的元素，那么此時數(shù)組無需移動其它元素义黎，即禾进，最好時間復(fù)雜度為 O(1) 。如果要刪除數(shù)組開頭的元素廉涕，為了保證數(shù)組的空間連續(xù)性泻云，需要將數(shù)組的后 n-1 個元素向前移動一個位置艇拍，即，最壞的時間復(fù)雜度為 O(n) 宠纯。如果要刪除數(shù)組的第 k 個位置的元素淑倾，需要將第 k+1~n 位置的元素向前移動一個位置，刪除位置的情況總共有 n 種征椒，假設(shè)刪除每個位置的元素的概率是一樣的娇哆，那么刪除第k個位置元素的平均時間復(fù)雜度就為：
T(n) = O(0) x+ O(1) x
) = O(
) = O(n)
4. 算法優(yōu)化
-
插入操作在特殊場景下的改進(jìn)
如果數(shù)組中存儲的數(shù)據(jù)沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個存儲數(shù)據(jù)的容器勃救。在這種情況下碍讨，為了避免大規(guī)模的數(shù)據(jù)搬移，在第 k 個位置插入數(shù)據(jù)蒙秒，有一個簡單的辦法就是勃黍，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個位置晕讲。這樣插入操作的時間復(fù)雜度就是 O(1) 覆获。
數(shù)組中插入元素 -
刪除操作在特殊場景下的改進(jìn)
在不考慮數(shù)據(jù)連續(xù)性的場景下，刪除操作同樣可以改進(jìn)瓢省，假設(shè)數(shù)組 a 的長度是5弄息，現(xiàn)要刪除第1，2勤婚，3位置的元素摹量，如果刪除三次的話，那么數(shù)組中剩余元素就要整體向前搬移3次馒胆。為了減少整體搬移的次數(shù)缨称，可以采樣標(biāo)記刪除法，即祝迂，當(dāng)要刪除第1位置的元素的時候睦尽，我們可以將這個位置的元素標(biāo)記一下，使之后的數(shù)組訪問操作訪問不到這個位置的元素型雳，而并不是真正的刪除当凡，當(dāng)刪除第2，3位置的做法一樣四啰。假如數(shù)組數(shù)據(jù)已經(jīng)存放滿了宁玫，而現(xiàn)在想要插入一個數(shù)據(jù)粗恢，這時就可以觸發(fā)一次刪除操作柑晒，一次性將標(biāo)記的1，2眷射，3位置的元素刪除匙赞，其余的元素整體向前移動三個位置佛掖，然后將新的元素插入空余的空間中。這樣就減少了元素搬移的次數(shù)涌庭，從而效率得到優(yōu)化芥被。
數(shù)組中刪除元素
5. 注意數(shù)組的越界
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
上述代碼的本意是打印3次“hello world”，但是由于條件寫成了i<=3坐榆，造成了數(shù)組訪問越界拴魄，使之變成了死循環(huán)，無限的打印“hello world”席镀。
從課程下方各位大神的留言中學(xué)習(xí)到匹中，此段代碼的執(zhí)行結(jié)果和編譯器有關(guān)，如果用來編譯這段代碼的編譯器是按照內(nèi)存地址遞減的方式給變量分配內(nèi)存的話豪诲，那么內(nèi)存中的 i 將會被置為 0顶捷，就會出現(xiàn)死循環(huán)∈豪椋可查看 《C陷阱與缺陷》 解惑服赎。
這種問題，debug 的難度非常的大交播。而且重虑，很多計算機病毒也正是利用到了代碼中的數(shù)組越界可以訪問非法地址的漏洞，來攻擊系統(tǒng)秦士，所以寫代碼的時候一定要警惕數(shù)組越界嚎尤。
6. 容器和數(shù)組
針對數(shù)組類型，很多語言都提供了容器類伍宦，比如 Java 中的 ArrayList芽死、C++ STL 中的 vector。如何更好的使用他們有以下幾點經(jīng)驗：
- 如果特別關(guān)注性能次洼，或者希望使用基本類型关贵，就可以選用數(shù)組。
- 如果數(shù)據(jù)大小事先已知卖毁，并且對數(shù)據(jù)的操作非常簡單揖曾，用不到一些容器提供的大部分方法，也可以直接使用數(shù)組亥啦。
- 要表示多維數(shù)組時炭剪，用數(shù)組往往會更加直觀。
- 對于業(yè)務(wù)開發(fā)翔脱，直接使用容器就足夠了奴拦，省時省力。畢竟損耗一丟丟性能届吁，完全不會影響到系統(tǒng)整體的性能错妖。
- 如果是做一些非常底層的開發(fā)绿鸣，比如開發(fā)網(wǎng)絡(luò)框架，性能的優(yōu)化需要做到極致暂氯，這個時候數(shù)組就會優(yōu)于容器潮模，成為首選。
上一篇：《數(shù)據(jù)結(jié)構(gòu)和算法之美》學(xué)習(xí)筆記 Day 3
下一篇：《數(shù)據(jù)結(jié)構(gòu)和算法之美》學(xué)習(xí)筆記 Day 5 待更新
