跳到正文

CSCI2100

數據結構

鏈表、堆疊與隊列、動態陣列、雜湊、優先隊列、二叉搜尋樹、平衡搜尋樹與多路搜尋樹、Trie、不相交集合、排序、圖算法及算法分析。

19 章 · 30 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 30 節已標記完成

下一節: 不相交集合:劃分、森林與並查集

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI2100 筆記裏的內容

定理卡
69
定義
41
反例
39
概念視角
20
思想史
0
證明透視
35

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 30 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 69 · 定義 41 · 反例 39 · 概念視角 20 · 證明透視 35

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 30 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 1 節

不相交集合

劃分與並查集

定理 3 · 定義 1反例 2視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    不相交集合:劃分、森林與並查集

    用父指標森林表示逐步合併的群組,證明連接根與路徑壓縮的正確性,並分析按大小合併。

第 2 章 · 3 節

線性數據結構

隊列不變量、攤銷分析及鏈表環偵測。

定理 7 · 定義 3反例 4視角 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    用兩個堆疊建立先進先出隊列

    證明隊列不變量,並計算偶爾昂貴的轉移成本。

  2. 2.2

    不用已訪集合找出鏈表中的環

    追蹤 Floyd 的指標,證明相遇原因,並定位及安全移除環。

  3. 2.3

    雙堆疊隊列:不變量與攤銷成本

    追蹤隊首觀察、轉移迴圈與攤銷成本。

第 3 章 · 2 節

優先隊列

堆不變量、插入及移除最小值。

定理 6 · 定義 2反例 2視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    二叉最小堆與優先隊列

    證明二叉最小堆不變量,分析插入及移除最小值。

  2. 3.2

    自底向上建立最小堆

    證明下濾的正確性及原地建立堆的線性時間界。

第 4 章 · 2 節

搜尋樹的次序統計量

維持子樹大小並按排名選取鍵。

定理 2 · 定義 2反例 2視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    在搜尋樹中按排名選取

    證明排名選取,並在插入、刪除及旋轉下維持子樹計數。

  2. 4.2

    選取最小的 k 個記錄

    以排名閾值選出恰好 k 個記錄,明確訂立平手、次序和成本。

第 5 章 · 2 節

雜湊

分離鏈結與碰撞的期望成本。

定理 3 · 定義 5反例 2視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    分離鏈結與碰撞的期望成本

    跟蹤鏈結查詢,並在逐對碰撞假設下證明期望界。

  2. 5.2

    線性探測與墓碑刪除

    追蹤有界探測並證明刪除與鍵唯一性的不變量。

第 6 章 · 1 節

概率式成員判定

Bloom 過濾器、保證及假陽性模型。

定理 2 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    Bloom 過濾器與假陽性

    區分確定性成員保證與理想化假陽性模型。

第 7 章 · 2 節

字串 Trie

精確成員、前綴列舉與安全剪枝。

定理 4 · 定義 2反例 2視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    Trie 前綴、終止標記與安全剪枝

    維護精確字串成員與前綴列舉,並證明刪除保留共用路徑。

  2. 7.2

    追蹤精確查找與前綴補全

    逐字追蹤 trie 查詢,區分到達節點與已儲存鍵值。

第 8 章 · 1 節

多路搜尋樹

在插入時維持 B 樹的佔用及搜尋不變量。

定理 3 · 定義 1反例 2視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    B 樹:不變量、分裂與由上而下插入

    定義多路搜尋樹的規格,證明子節點分裂及插入正確,追蹤二階例子,並區分高度、比較及區塊讀取成本。

第 9 章 · 1 節

自調整搜尋樹

伸展旋轉與攤銷存取證明。

定理 3 · 定義 2反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    伸展樹:旋轉與存取引理

    追蹤伸展操作並證明無權攤銷存取界。

第 10 章 · 2 節

鏈表不變量

哨兵環、節點所屬關係與拼接的代價。

定理 3 · 定義 2反例 3視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 10.1

    哨兵鏈表與節點拼接

    從局部連結推導整體成員關係,並計算搜尋與維護大小的代價。

  2. 10.2

    遞歸刪除與回傳的表頭

    追蹤節點所有權與元數據,證明遞歸刪除的規格。

第 11 章 · 1 節

動態陣列

幾何擴縮容與攤銷成本。

定理 2 · 定義 1反例 2視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 11.1

    動態陣列與攤銷成本

    追蹤擴縮容並證明攤銷更新界。

第 12 章 · 1 節

有序陣列搜尋

邊界搜尋與迴圈不變量。

定理 3 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 12.1

    二分搜尋:邊界與迴圈不變量

    證明上下界,處理重複值並分析存取成本。

第 13 章 · 2 節

圖遍歷

用隊列和發現標記尋找無權圖最短路徑。

定理 5 · 定義 3反例 4視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 13.1

    廣度優先搜尋:隊列與最短路徑

    追蹤入隊標記,證明層次不變量並重建無權圖最短路徑。

  2. 13.2

    圖的表示法與深度優先搜尋

    比較鄰接矩陣與鄰接表,並分析深度優先搜尋:時間戳、邊的分類、環偵測與拓撲次序。

第 14 章 · 2 節

圖算法

最小生成森林與並查集。

定理 7 · 定義 4反例 3視角 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 14.1

    Kruskal 算法:並查集與最小生成森林

    證明森林不變量和貪婪割交換,並追蹤按大小合併。

  2. 14.2

    加權圖的前沿:Dijkstra 與 Prim

    在同一加權圖上追蹤使用惰性堆的 Dijkstra 算法及 Prim 算法,並證明各自選取步驟的安全性。

第 15 章 · 2 節

平衡搜尋樹

AVL 樹與紅黑樹:高度界及更新後的修復。

定理 5 · 定義 2反例 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 15.1

    AVL 樹:高度、旋轉與刪除

    證明對數高度界,以旋轉保留搜尋次序,並逐步分析插入及向上連鎖的刪除修復。

  2. 15.2

    紅黑樹:黑高度與插入修復

    從顏色不變量推導對數搜尋深度,證明各種插入修復,並分清重新着色與旋轉的代價。

第 16 章 · 1 節

雜湊表與通用雜湊

鏈結法、期望鏈長與通用雜湊族。

定理 2 · 定義 2反例 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 16.1

    雜湊表:鏈結法、通用雜湊與期望成本

    在碰撞中保留映射,以指示變量證明期望鏈長,並用質數模運算建立通用雜湊族。

第 17 章 · 1 節

二叉搜尋樹

普通二叉搜尋樹的次序不變量與刪除。

定理 2 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 17.1

    二叉搜尋樹刪除:後繼節點、子樹回傳與節點身分

    以後繼節點取代法刪除二叉搜尋樹的鍵,回傳新的子樹根,並檢驗次序不變量與成本。

第 18 章 · 2 節

排序

鏈表上的合併排序、陣列合併排序、快速排序與比較排序下界。

定理 5 · 定義 4反例 2視角 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 18.1

    鏈表上的合併排序:正確性同樣關乎連結

    以破壞性且穩定的方式合併已排序鏈表,用快慢指標分割鏈表,並分析鏈表上的合併排序。

  2. 18.2

    比較排序:合併排序、快速排序與下界

    以不變量與遞推式分析陣列上的合併排序和快速排序,並證明任何比較排序都需要約 n log n 次比較。

第 19 章 · 1 節

算法分析

成本模型與漸進記號。

定理 2 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 19.1

    漸進記號與成本模型

    固定成本模型,以明確的常數定義 O、Omega 與 Theta,並推導簡單迴圈程式碼的增長類別。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情