文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載本文基于 CLRSIntroduction to Algorithms第三版習題解答倉庫中的 docs/Chap02/2.1.md完整梳理第 2.1 節(jié)四道習題2.1-1 至 2.1-4的解答對數組 $\langle 31, 41, 59, 26, 41, 58 \rangle$ 逐步圖解INSERTION-SORT的執(zhí)行過程、改寫為降序排序的偽代碼修改、用循環(huán)不變量loop invariant嚴格證明線性搜索的正確性以及兩個 $n$ 位二進制整數相加的形式化問題定義與偽代碼。讀完本篇你將掌握用執(zhí)行軌跡驗證排序算法用循環(huán)不變量三要素證明算法正確性這兩項算法分析與證明的核心技能。背景標準版 INSERTION-SORT 偽代碼第 2.1 節(jié)習題均以教材中的INSERTION-SORT過程為討論對象。為與原文中提到的第 5 行的測試第 6 行的移動第 8 行的放置對應先給出帶行號的偽代碼這是 CLRS 教材 Section 2.1 的標準形式數組下標從 1 開始INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key該算法維護的核心循環(huán)不變量是每次 for 循環(huán)迭代開始時子數組 $A[1..j-1]$ 恰好是原始 $A[1..j-1]$ 中元素的非遞減排序版本。每一輪從 $A[j]$ 取出key在它左邊已排序的前綴中通過while循環(huán)不斷右移比它大的元素最終把key放到正確位置——這正是下文 2.1-1 圖解要展示的過程。本倉庫是面向 CLRS 習題的開源解答合集采用 Markdown KaTeX 編寫、由 MkDocsMaterial for MkDocs 主題構建為靜態(tài)網站參見 mkdocs.yml 的導航中2.1 Insertion sort: Chap02/2.1.md一項以及 README.md 對構建方式的說明。下面按原題順序展開解答并對關鍵結論補充推導與復雜度依據。2.1-1 圖解 INSERTION-SORT 對 $\langle 31, 41, 59, 26, 41, 58 \rangle$ 的執(zhí)行題目以教材 Figure 2.2 為模型圖解INSERTION-SORT在數組 $A \langle 31, 41, 59, 26, 41, 58 \rangle$ 上的執(zhí)行過程。下圖來自倉庫中的 docs/img/2.1-1-1.png矩框上方是下標、框內是存儲值圖中各子圖的讀法與解答文檔一致(a)–(e) 對應第 2 行 for 循環(huán)的 5 次迭代即 $j 2, 3, 4, 5, 6$每輪中黑色矩形是取自 $A[i]$即 $A[j]$的key它與左側灰色陰影矩形中的值進行第 5 行的比較測試虛線箭頭表示第 6 行把元素值向右移動一格實線箭頭表示第 8 行key最終落到的位置(f)是最終排序完成的數組。逐輪看(a) 取 $A[2] 41$ 為 key左側僅 $31$無需移動(b) 取 $A[3] 59$仍無需移動(c) 取 $A[4] 26$while循環(huán)連續(xù) 3 次比較、把 $59, 41, 31$ 依次右移一格key落入 $A[1]$(d) 取第二個 $41$$A[5]$只把 $A[4]$ 處的 $59$ 右移一格(e) 取 $A[6] 58$把 $A[5]$ 處的 $59$ 右移一格(f) 得到 $\langle 26, 31, 41, 41, 58, 59 \rangle$。原文檔同時列出了數組 $A$ 在遍歷過程中的逐輪變化這里整理為帶輪次標注的表格下標均從 1 計迭代key迭代結束后數組狀態(tài)初始—$A \langle 31, 41, 59, 26, 41, 58 \rangle$$j 2$$41$$A \langle 31, 41, 59, 26, 41, 58 \rangle$不變$j 3$$59$$A \langle 31, 41, 59, 26, 41, 58 \rangle$不變$j 4$$26$$A \langle 26, 31, 41, 59, 41, 58 \rangle$$j 5$$41$$A \langle 26, 31, 41, 41, 59, 58 \rangle$$j 6$$58$$A \langle 26, 31, 41, 41, 58, 59 \rangle$從這份軌跡可以直觀看出插入排序的運行時間特征第 $j$ 輪的工作量取決于while循環(huán)第 5–7 行右移了多少個元素。輸入已經有序時每輪只做一次失敗比較總時間為 $\Theta(n)$輸入逆序時每輪右移 $j-1$ 個元素總時間為 $\Theta(n^2)$。倉庫中 docs/Chap02/Problems/2-4.md 進一步給出了一個漂亮的刻畫while循環(huán)總共執(zhí)行的次數恰好等于輸入數組的逆序對inversion總數因此插入排序的運行時間與逆序數成正比——本題中 $j4$ 時key26右移了 3 個元素正對應它新引入的 3 個逆序對。2.1-2 改寫為按非遞增降序排序題目把INSERTION-SORT改寫為按非遞增序nonincreasing排序。標準版之所以產生升序是因為第 5 行while的條件A[i] key讓比 key 大的元素不斷右移。要得到降序只需把比較方向反過來——讓比 key 小的元素右移INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key唯一改動就是比較運算符由變?yōu)?。其余結構取 key、回退掃描、右移、落位完全不變因此循環(huán)不變量相應改為每次迭代開始時 $A[1..j-1]$ 是原始前綴的非遞增排序版本。用同一輸入驗證對 $A \langle 31, 41, 59, 26, 41, 58 \rangle$ 執(zhí)行降序版最終得到 $\langle 59, 58, 41, 41, 31, 26 \rangle$。另外值得注意的一個細節(jié)條件取嚴格小于而非 $\le$意味著遇到與key相等的元素時while循環(huán)立即停止、不再繼續(xù)左移因此相同值的元素保持其在輸入中的相對順序——這個降序版本對相等元素是穩(wěn)定的與升序版本使用嚴格大于的設計意圖一致。2.1-3 線性搜索的偽代碼與基于循環(huán)不變量的正確性證明題目搜索問題輸入$n$ 個數的序列 $A \langle a_1, a_2, \ldots, a_n \rangle$ 和一個值 $v$輸出滿足 $v A[i]$ 的下標 $i$若 $v$ 不在 $A$ 中則返回特殊值NIL。要求寫出掃描序列尋找 $v$ 的**線性搜索linear search**偽代碼并用循環(huán)不變量證明其正確性且證明須完整覆蓋循環(huán)不變量的三個必要性質初始化、保持、終止。偽代碼解答LINEAR-SEARCH(A, v) for i 1 to A.length if A[i] v return i return NIL循環(huán)不變量在 for 循環(huán)每次迭代開始時子數組 $A[1..i-1]$ 中的元素都與 $v$ 不相等。下面按三要素展開這是原文檔的證明主體完整保留其論證鏈條初始化Initialization第一次迭代之前 $i 1$子數組 $A[1..0]$ 是空數組所有元素都不等于 $v$這一陳述平凡成立故不變量初始為真。保持Maintenance每次迭代把 $v$ 與 $A[i]$ 比較。若相等立即return i——由于 $A[i]$ 之前的位置在不變量下已知不含 $v$返回的下標就是正確答案若不等本輪結束后已知 $A[1..i]$ 不含 $v$$i$ 自增 1 后新迭代開始時 $A[1..i-1]$即舊的 $A[1..i]$仍滿足不變量故不變量得以保持到下一輪。終止Termination循環(huán)在 $i A.length n$ 時終止。由于 $i$ 每次恰好加 1終止時必有 $i n 1$。把 $n1$ 代入不變量的表述得到子數組 $A[1..n]$即整個數組中所有元素都不等于 $v$此時執(zhí)行return NIL是正確的。綜上算法正確。這個證明展示了循環(huán)不變量方法的完整范式不變量描述循環(huán)之前已經完成了什么終止時把不變量代入終態(tài)即得結論。它與INSERTION-SORT的不變量前綴有序同屬一種技術區(qū)別只在于斷言的內容從有序換成了不含目標值。關于復雜度倉庫中 docs/Chap02/2.2.md 的習題 2.2-3 給出了配套分析若目標等概率地是數組中任意元素平均需要檢查 $n/2$ 個元素最壞需要檢查全部 $n$ 個兩者都是 $\Theta(n)$。此外 docs/Chap02/2.3.md 的習題 2.3-5 指出當序列已排序時可改用二分搜索每次比較砍掉一半搜索空間最壞時間為 $\Theta(\lg n)$——這與本題的線性搜索形成對照。2.1-4 兩個 n 位二進制整數相加形式化問題與偽代碼題目考慮把兩個 $n$ 位二進制整數相加的問題兩個整數分別存放在 $n$ 元素數組 $A$ 和 $B$ 中和以二進制形式存入 $(n1)$ 元素數組 $C$。要求形式化地陳述問題并寫出偽代碼。形式化陳述原文檔的解答注意其約定的位序輸入布爾數組 $A \langle a_1, a_2, \ldots, a_n \rangle$ 與 $B \langle b_1, b_2, \ldots, b_n \rangle$各表示一個以二進制存儲的整數最低有效位在前l(fā)east-significant digit first即 $a_1, b_1$ 是最低位輸出數組 $C \langle c_1, c_2, \ldots, c_{n1} \rangle$使得 $C A B$其中 $A$、$B$、$C$ 是三個數組各自表示的整數。偽代碼模擬手工豎式加法從低位到高位逐位相加并傳遞進位ADD-BINARY(A, B) carry 0 for i 1 to A.length sum A[i] B[i] carry C[i] sum % 2 // remainder carry sum / 2 // quotient C[A.length 1] carry return C正確性與復雜度可以從實現層面進一步確認由于 $a_i, b_i \in {0, 1}$ 且進位carry取值只能是 $0$ 或 $1$因為 $sum \le 3$sum / 2向下取整后最多為 $1$所以carry在循環(huán)中始終被維持在 ${0, 1}$ 中與十進制豎式加法中進位是單個數字完全同構循環(huán)體只做常數次算術操作總時間 $\Theta(n)$?？臻g上兩個 $n$ 位數的和最大為 $2^{n} - 1 2^{n} - 1 2^{n1} - 2$恰好需要 $n1$ 位表示這正是輸出數組長度為 $n1$ 的原因——最高位 $C[n1]$ 只可能是最終的進位值 $0$ 或 $1$。若輸入約定改為最高位在前則需把循環(huán)方向改為從下標 $n$ 遞減到 $1$其余邏輯不變。小結與延伸閱讀本篇覆蓋了 docs/Chap02/2.1.md 的四道習題四個主題恰好串起算法學習的基本功2.1-1以具體數組逐步圖解插入排序理解取 key → 比較右移 → 落位的執(zhí)行模型2.1-2通過翻轉單個比較方向得到降序版本體會偽代碼中比較條件與循環(huán)不變量的對應關系2.1-3用初始化/保持/終止三要素以循環(huán)不變量嚴格證明線性搜索正確性2.1-4把二進制加法形式化為數組運算用單個進位變量在線性時間完成。想繼續(xù)深入時建議按以下倉庫內文檔延伸docs/Chap02/2.2.md第 2.2 節(jié)習題——算法分析$\Theta$ 記號、選擇排序的循環(huán)不變量與運行時間、線性搜索的平均/最壞情況分析docs/Chap02/2.3.md第 2.3 節(jié)習題——歸并排序圖解、二分搜索以及習題 2.3-6 的結論把插入排序的while掃描換成二分搜索并不能把最壞時間降到 $\Theta(n\lg n)$因為右移元素本身仍要 $\Theta(j)$ 時間搜索只是次要開銷docs/Chap02/Problems/2-1.md問題 2-1——在歸并排序的小子表上改用插入排序的混合策略及其閾值 $k \Theta(\lg n)$ 的推導docs/Chap02/Problems/2-4.md問題 2-4——逆序對與插入排序運行時間的精確關系以及用改造版歸并排序在 $\Theta(n\lg n)$ 內統(tǒng)計逆序對數。贊分享文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載相關推薦CLRS 第 2.1 章習題精解插入排序、線性查找與 n 位二進制加法含 Python 實現CLRS 第 2.1 章習題精解插入排序、線性查找與 n 位二進制加法含 Python 實現 本篇技術指南圍繞《算法導論》Introduction to文檔教程示例工程magvit2-pytorch從零訓練VideoTokenizer新手也能上手的完整實戰(zhàn)教程magvit2 pytorch從零訓練VideoTokenizer新手也能上手的完整實戰(zhàn)教程 想要從零訓練一個屬于自己的 VideoTokenizer視頻分CLRS 第二章 2.2 習題詳解Θ 記號、選擇排序、線性搜索與最好情況優(yōu)化CLRS 第二章 2.2 習題詳解Θ 記號、選擇排序、線性搜索與最好情況優(yōu)化 導讀 本篇基于《算法導論》CLRS習題解答倉庫中的 2.2.md https文檔教程示例工程上一篇3分鐘解決OpenDrop傳輸卡頓從網卡配置到代碼優(yōu)化全指南下一篇2025最新awesome-emacs項目解析社區(qū)精選Emacs包與工具大全創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考