@time 2019-07-18 @author Ruo_Xiao @notice 64位OS

一、基礎(chǔ)知識(shí)

1、數(shù)組的定義

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間來存儲(chǔ)一組具有相同數(shù)據(jù)類型的數(shù)據(jù)。

2、連續(xù)的內(nèi)存空間和相同的數(shù)據(jù)類型

這種數(shù)據(jù)的組織方式，直接導(dǎo)致了數(shù)據(jù)具有核心特性：隨機(jī)訪問。

實(shí)現(xiàn)公式（尋址公式）如下：

a[i]_address = a_address + i * type_size

通過上述公式，也能夠明白為什么數(shù)組的下標(biāo)為什么從0開始。若從1開始的話，那么上述公式就變成了?

a[i]_address = a_address + （i - 1） * type_size

像數(shù)組這種編程語言最底層的數(shù)據(jù)結(jié)構(gòu)，性能必須優(yōu)化到極致，所以采用了下標(biāo)從0開始的模式。?

拓展：二維數(shù)組的尋址公式為

// 假設(shè)二位數(shù)組為 m * n a[i][k]_address = a_address + (i * n + k) * type_size

二、相關(guān)操作

為了保持內(nèi)存空間的連續(xù)性，數(shù)組的插入和刪除是低效的，因?yàn)椴僮髦笠M(jìn)行數(shù)據(jù)遷移。

1、插入

• 插入的位置在隊(duì)尾，時(shí)間復(fù)雜度為 O(1) 。
• 插入的位置在隊(duì)首，時(shí)間復(fù)雜度為 O(n)。
• 平均復(fù)雜度，因?yàn)椴迦氲奈恢檬请S機(jī)的，即：概率相同。所以，平均復(fù)雜度為

(1 + 2 + 3 + …… + n) / n = ( n + 1 ) * n / ( 2 * n ) =?(1/2)n + (1/2) = O(n)

• 如果對數(shù)組的順序沒有要求，那么可以將插入的位置的原數(shù)據(jù)放入數(shù)組末尾，將新數(shù)據(jù)賦值到該位置，時(shí)間復(fù)雜度為O(1) 。為 O(1) 的原因是該操作不會(huì)隨著數(shù)組元素?cái)?shù)量的變大而變大，執(zhí)行的指令數(shù)量相同，所以復(fù)雜度為 O(1) 。

2、刪除

• 刪除的位置在隊(duì)尾，時(shí)間復(fù)雜度為 O(1) 。
• 刪除的位置在隊(duì)首，時(shí)間復(fù)雜度為 O(n)。
• 平均復(fù)雜度為 O(n) 。計(jì)算過程參考 “插入”?部分。
• 很多時(shí)候，為了追求軟件性能，可以將數(shù)組中待刪除的數(shù)據(jù)標(biāo)記為已刪除狀態(tài)，然后定時(shí)對已經(jīng)刪除的數(shù)據(jù)進(jìn)行集中刪除操作，這種思想類似于 JVM 的垃圾回收機(jī)制。

? ? ? ? 其實(shí)上述操作，在 C++ 中 vector 早已封裝好，所以在 C++ 編程中，推薦使用vector代替數(shù)組。當(dāng)然了，那些對于性能有卓越的追求的領(lǐng)域，數(shù)組還是無可替代的。

?

?

（SAW：Game Over！）

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法 / 数组（Array）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。