算法詳解四部曲第一卷，詳解算法基礎，展現算法本質集斯坦福大學教授多年教學經驗，深入淺出，通俗易懂算法是計算機科學的核心與靈魂。算法的應用範圍極廣，網絡路由、計算基因組學、公鑰加密學和數據庫繫統等的實現都需要算法。研究算法可以幫助我們成為更優秀的程序員，可以讓我們具有更縝密的思維，並成功應對各種場合的技術面試。這是一本非常容易上手的算法入門圖書，它可作為程序員的學習用書，也適合想要學習算法和想提升算法思維能力的讀者閱讀。本書主要包括以下內容：漸進性分析；大O表示等

●第 1章 緒論11.1 為什麼要學習算法11.2 整數乘法31.2.1 問題和解決方案31.2.2 整數乘法問題31.2.3 小學算法41.2.4 操作數量的分析51.2.5 還能做得更好嗎51.3 Karatsuba乘法61.3.1 一個具體的例子61.3.2 一種遞歸算法71.3.3 Karatsuba乘法91.4 MergeSort算法111.4.1 推動力111.4.2 排序121.4.3 一個例子131.4.4 偽碼141.4.5 Merge子程序151.5 MergeSort算法分析161.5.1 Merge的運行時間171.5.2 MergeSort的運行時間181.5.3 定理1.2的證明191.5.4 小測驗1.1～1.2的答案231.6 算法分析的指導原則231.6.1 第 1個原則：最壞情況分析241.6.2 第 2個原則：全局分析251.6.3 第3個原則：漸進性分析261.6.4 什麼是“快速”算法271.7 本章要點281.8 習題29挑戰題31編程題31第 2章 漸進性表示法322.1 要旨322.1.1 推動力322.1.2 高級思維332.1.3 4個例子342.1.4 小測驗2.1～2.4的答案382.2 大O表示法402.2.1 文本定義402.2.2 圖形定義402.2.3 數學定義412.3 兩個基本例子422.3.1 k階多項式是O(nk)422.3.2 k階多項式不是O(nk-1)432.4 大Ω和大 表示法442.4.1 大Ω表示法442.4.2 大 表示法452.4.3 小O表示法462.4.4 漸進性表示法的來源472.4.5 小測驗2.5的答案482.5 其他例子482.5.1 在指數中添加一個常數482.5.2 指數乘以一個常數492.5.3 優選值vs.和492.6 本章要點502.7 習題51第3章 分治算法533.1 分治法規範533.2 以O(n log n)時間計數逆序對543.2.1 問題543.2.2 一個例子543.2.3 協同篩選553.2.4 窮舉搜索法553.2.5 分治法563.2.6 高級算法573.2.7 關鍵思路：站在MergeSort的肩膀上573.2.8 重溫Merge583.2.9 Merge和分離逆序對603.2.10 Merge_and_CountSplitInv613.2.11 正確性613.2.12 運行時間623.2.13 小測驗3.1～3.2的答案623.3 Strassen的矩陣相乘算法633.3.1 矩陣相乘633.3.2 例子（n = 2）643.3.3 簡單算法643.3.4 分治法653.3.5 一個遞歸調用673.3.6 細節683.3.7 小測驗3.3的答案69*3.4 O(n log n)時間的最近點對（Closest Pair）算法703.4.1 問題703.4.2 熱身：1D情況713.4.3 預處理713.4.4 一種分治方法723.4.5 一個微妙的變化743.4.6 ClosestSplitPair743.4.7 正確性763.4.8 輔助結論3.3（a）的證明773.4.9 輔助結論3.3（b）的證明783.4.10 小測驗3.4的答案803.5 本章要點803.6 習題81挑戰題81編程題82第4章 主方法834.1 重溫整數乘法834.1.1 RecInt lt算法844.1.2 Karatsuba算法844.1.3 比較遞歸過程854.2 形式聲明864.2.1 標準遞歸過程864.2.2 主方法的陳述和討論874.3 6個例子884.3.1 重溫MergeSort894.3.2 二分搜索894.3.3 整數乘法的遞歸算法904.3.4 Karatsuba乘法904.3.5 矩陣乘法914.3.6 一個虛構的遞歸過程924.3.7 小測驗4.2～4.3的答案93*4.4 主方法的證明944.4.1 前言944.4.2 重溫遞歸樹954.4.3 單層所完成的工作964.4.4 各層累計974.4.5 正義與邪惡：需要考慮3種情況984.4.6 預告運行時間上界994.4.7 最後的計算：第 一種情況1004.4.8 迂回之旅：幾何級數1014.4.9 最後的計算：第二種情況和第三種情況1024.4.10 小測驗4.4～4.5的答案1034.5 本章要點1034.6 習題104第5章 快速排序（QuickSort）1075.1 概述1075.1.1 排序1085.1.2 根素進行劃分1085.1.3 高級描述1105.1.4 內容前瞻1105.2 圍素進行劃分1115.2.1 簡易方法1115.2.2 原地實現：高級計劃1125.2.3 例子1135.2.4 Partition子程序的偽碼1155.2.5 QuickSort的偽碼1175.3 良好素的重要性1175.3.1 ChoosePivot的簡單實現1185.3.2 ChoosePivot的過度實現1185.3.3 小測驗5.1～5.2的答案1195.4 隨機化的QuickSort1215.4.1 ChoosePivot的隨機化實現1215.4.2 隨機化QuickSort的運行時間1225.4.3 直覺：隨素為什麼很好123*5.5 隨機化QuickSort的分析1245.5.1 預備工作1255.5.2 分解藍圖1265.5.3 應用藍圖1285.5.4 計算比較的概率1305.5.5 最後的計算1325.5.6 小測驗5.3的答案133*5.6 排序需要 (n log n)的比較1345.6.1 基於比較的排序算法1345.6.2 具有更強前提的更快速排序1355.6.3 定理5.5的證明1365.7 本章要點1385.8 習題139挑戰題140編程題141第6章 線性時間級的選擇1426.1 RSelect算法1436.1.1 選擇問題1436.1.2 簡化為排序1446.1.3 分治法1456.1.4 RSelect的偽碼1466.1.5 RSelect的運行時間1476.1.6 小測驗6.1～6.2的答案149*6.2 RSelect的分析1506.2.1 根據階段追蹤進展1506.2.2 簡化為擲硬幣1516.2.3 綜合結論153*6.3 DSelect算法1546.3.1 基本思路：中位素1546.3.2 DSelect的偽碼1556.3.3 理解DSelect1566.3.4 DSelect的運行時間157*6.4 DSelect的分析1596.4.1 遞歸調用之外所完成的工作1596.4.2 一個粗略的遞歸過程1596.4.3 30-70輔助結論1606.4.4 解析遞歸過程1636.4.5 先猜後驗方法1646.5 本章要點1666.6 本章習題166挑戰題167編程題168附錄A 快速回顧數學歸納法169附錄B 快速回顧離散概率173

算法是計算機科學領域最重要的基石之一。算法是程序的靈魂，隻有掌握了算法，纔能輕松地駕馭程序開發。算法詳解繫列圖書共有4卷，本書是第1卷——算法基礎。本書共有6章，主要介紹了4個主題，它們分別是漸進性分析和大O表示法、分治算法和主方法、隨機化算法以及排序和選擇。附錄A和附錄B簡單介紹了數據歸納法和離散概率的相關知識。本書的每一章均有小測驗、章末習題和編程題，這為讀者的自我檢查以及進一步學習提供了較多的便利。本書為對算法感興趣的廣大讀者提供了豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生，想要培養和訓練算法思維和計算思維的IT專業人士，以及在準備面試的應聘者和面試官閱讀參考。

[美]蒂姆·拉夫加登（Tim Roughgarden） 著 徐波 譯