高階資料結構與演算法

這是一本補充資料結構 手冊和演算法 手冊的書籍，並假定這些手冊作為先決條件。

線上書籍寫作有兩個相互衝突的目標

• 作為對基礎材料的介紹
• 成為包含對切線材料的討論的完整參考作品

我們決定兩者都做。資料結構 文字和演算法 文字僅關注基礎知識。本手冊（高階資料結構與演算法）是參考材料的地方。其想法是，學生在一年或更短的時間內可以涵蓋這些基礎知識，然後繼續學習本書中的高階主題。

可能的話題

• 並行程式設計（部分；對分治的闡述，或用於流式演算法的管道解耦）
• 記憶體管理和垃圾回收（整章）
• NP 完全性（整章）
• 主定理的證明（部分）
• 四叉樹和 八叉樹 以及 R 樹（章）
• Trie 資料結構
• B 樹（章）（我們不是已經介紹過這個主題了嗎？請參閱 資料結構/樹#B 樹 和 演算法實現/樹/B+ 樹 ？）
• （偽）隨機數生成器（請參閱 統計/數值方法/隨機數生成 等）
• 自省排序（部分；一種混合排序演算法）
• 閉包（ 什麼是閉包？ ）
• 延續（ 延續 ）
• 快取感知和快取無關演算法
• 近似
• 最大流
• 素數測試（請參閱 演算法實現/數學/素數測試，演算法實現/數學/素數生成，一些基本且低效的素數生成演算法，密碼學/數學背景#素數測試，離散數學/數論#素數測試，密碼學/RSA#金鑰生成 等）

雖然這裡還沒有內容，但請隨時開始編寫部分！因為本書更像是一本參考書，所以章節之間可以更加獨立。此外，您可以假設讀者已經瞭解基本的資料結構和演算法。

FFT 乘法*

如演算法手冊中所述，透過將一個整數分成兩部分並將其視為一個多項式，我們能夠推匯出一個比小學乘法更好的演算法。如果我們將整數分成三部分，則效率將進一步提高。然而，我們不需要止步於此：我們可以透過將一個n 位二進位制數分成一個n 次多項式來推廣多項式乘法和插值的技巧，從而將該數字分解成其各個數字（這也是我們能夠將此類數字分割的最遠端度）。

我們注意到，在點 1、-1 和 0 處對多項式表示進行求值使得表示式變得容易，但是如果我們要使用n 次多項式，我們該如何獲得足夠的點來使用呢？訣竅是使用複數對多項式進行求值，特別地，使用“單位根”：即所有距離原點為 1 的複數。

Trie 資料結構

Trie，也稱為數字樹，有時也稱為基數樹或字首樹（因為它們可以按字首進行搜尋），是一種有序的樹形資料結構，通常用於儲存關聯陣列，其中鍵通常是字串。與 二叉搜尋樹 不同，樹中的任何節點都沒有儲存完整的鍵。

樹列表

w:Rope (計算機科學)

在處理列表時，我們通常有兩種選擇：要麼我們獲得 $O(1)$ 索引訪問，但 $O(N)$ 插入，使用向量，或者 $O(N)$ 索引和 $O(1)$ 插入，使用連結串列。如果我們能夠找到一些中間地帶，比如所有操作的執行時間為 $O(\log N)$（攤銷）那該有多好。好吧，Soren Sandmann 已經實現了 GSequence，它使用伸展樹來實現這一點。[TODO: 該結構還沒有廣泛接受的名稱。如果有人能想到更好的名稱，請建議。]

我認為 B 樹演算法在最壞情況下提供 O(ln(N)) 插入、刪除和按名稱訪問。GSequence 在某些方面是否更好？我聽說一些作業系統將檔案和目錄儲存在磁碟上，作為 B 樹。--DavidCary 23:39, 21 July 2005 (UTC)

有很多平衡樹可以提供 O(ln N) 的效能。這裡的意思只是圍繞樹包裝一個列表介面。你也可以說你使用的是樹，因為列表介面只是為了實現方便。

有各種堆資料結構可以提供 O(log(N)) 插入、刪除和按名稱訪問。

我相信這些被稱為隨機訪問列表。此外，也可以實現 O(1) 插入和 O(log N) 索引；例如，Okasaki 的傾斜二項式隨機訪問列表。如果有興趣，我可以上傳一個 Common Lisp 中的演示質量實現。