《數(shù)據(jù)結(jié)構(gòu)與算法之美》讀書筆記

寫在前面

這本書的大部分內(nèi)容比較淺顯，因此只挑DSAA課程上沒有涉及或沒有深入討論的點(diǎn)總結(jié)

第二章

數(shù)組相關(guān)

1. 提高傳統(tǒng)數(shù)組插入/刪除數(shù)據(jù)效率的方法：

   • 如果插入的數(shù)據(jù)不要求有序，可以直接把某位的原數(shù)據(jù)替換成新數(shù)據(jù)，然后把原數(shù)據(jù)放到數(shù)組末尾，避免大面積的數(shù)據(jù)移動(dòng)。
   • 刪除時(shí)不用一個(gè)一個(gè)刪，可以先把要?jiǎng)h的元素一個(gè)個(gè)標(biāo)記好，等到數(shù)組中沒有更多的存儲(chǔ)空間時(shí)一并集中刪除。

2. 警惕C語言中數(shù)組訪問越界的問題，通過內(nèi)存公式計(jì)算出的內(nèi)存地址是可用的，即便越界，程序也可能不報(bào)任何錯(cuò)。

3. 容器（ArrayList/vector）VS 傳統(tǒng)數(shù)組：

   • 容器好用，上手快，封裝性強(qiáng)，但有時(shí)需要裝箱拆箱，存在性能損失。
   • 插入數(shù)據(jù)時(shí)的擴(kuò)容操作隱藏了復(fù)雜度，一行操作可能實(shí)際上遠(yuǎn)遠(yuǎn)不止。
   • 對(duì)于底層的開發(fā)，性能優(yōu)化需要做到極致，數(shù)組優(yōu)于容器。

C和Java數(shù)組的實(shí)現(xiàn)方式

• C/C++的多維數(shù)組也是從前往后連續(xù)存儲(chǔ)，Java則是存儲(chǔ)對(duì)象的引用。

• JavaScript根據(jù)存儲(chǔ)內(nèi)容動(dòng)態(tài)選擇存儲(chǔ)結(jié)構(gòu)，可利用ArrayBuffer進(jìn)行底層開發(fā)。

第三章

遞歸

1. 堆棧溢出不一定是死循環(huán)，可能是遞歸太深，棧裝不下了。

2. 遞歸時(shí)常常會(huì)不小心重復(fù)計(jì)算，可以使用哈希表等事先檢測是否已求解過。

3. 尾遞歸可避免堆棧溢出，但在實(shí)際軟件開發(fā)中并沒有多大用途。

排序

1. 穩(wěn)定排序與非穩(wěn)定排序：穩(wěn)定排序保持相同元素相對(duì)順序不變。

2. 歸并排序雖穩(wěn)定但空間復(fù)雜度高，通常不如快速排序?qū)嵱谩?/p>

3. 線性排序：

   • 桶排序：適用于數(shù)據(jù)易于劃分成若干個(gè)桶的場景，需注意內(nèi)存占用和數(shù)據(jù)范圍。

   • 計(jì)數(shù)排序：桶內(nèi)數(shù)據(jù)相同，適用于高考分?jǐn)?shù)等場景，注意處理負(fù)數(shù)和時(shí)間復(fù)雜度。

   • 基數(shù)排序：要求每位排序使用穩(wěn)定排序算法，時(shí)間復(fù)雜度近似O(n)。