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

寫在前面

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

第二章

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

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

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

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

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

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

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

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

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

第三章

遞歸

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

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

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

排序

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

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

3. 線性排序：

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

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

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