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