序言 第　1 章 絕不會(huì)輸?shù)馁�博　1 1.1　擲骰子　1 1.2　拋硬幣　4 1.2.1　兩枚硬幣　4 1.2.2　一枚硬幣　7 1.2.3　彩票的記憶　8 1.3　蒙提霍爾問(wèn)題　11 1.3.1　3 個(gè)信封　11 1.3.2　上帝視角　18 第　2 章 積跬步，致千里　21 2.1　高中　21 2.1.1　泰朵拉　21 2.1.2　理紗　22 2.1.3　順序查找　24 2.1.4　逐行調(diào)試　28 2.1.5　順序查找算法分析　34 2.1.6　順序查找算法分析（能找到v 的情況）　35 2.1.7　順序查找算法分析（無(wú)法找到v 的情況）　38 2.2　算法分析　40 目　錄 C　O N T E N T S 2　目錄 2.2.1　米爾嘉　40 2.2.2　算法分析　41 2.2.3　不同情況的歸納　42 2.2.4　思考意義　45 2.2.5　帶有哨兵的順序查找算法　48 2.2.6　創(chuàng)造歷史　52 2.3　自己家　54 第3　章 171億7986萬(wàn)9184份孤獨(dú)　61 3.1　排列　61 3.1.1　書(shū)店　61 3.1.2　豁然開(kāi)朗　62 3.1.3　具體示例　63 3.1.4　找規(guī)律　65 3.1.5　一般化　70 3.1.6　鋪就道路　72 3.1.7　那家伙　74 3.2　組合　76 3.2.1　圖書(shū)室　76 3.2.2　排列　77 3.2.3　組合　79 3.2.4　鱺魚(yú)與綠鯉魚(yú)　82 3.2.5　二項(xiàng)式定理　83 3.3　2n 的分配　88 3.3.1　帕斯卡三角形　88 3.3.2　位模式　92 目錄　3 3.3.3　指數(shù)爆炸　94 3.4　冪運(yùn)算的孤獨(dú)　96 3.4.1　回家路上　96 3.4.2　家　96 第4　章 可能性中的不確定性　99 4.1　可能性中的確定性　99 4.2　可能性中的不確定性　106 4.2.1　相同的可能性　106 4.2.2　真正的武器　107 4.3　可能性的實(shí)驗(yàn)　109 4.3.1　解釋程序　109 4.3.2　擲骰子比賽　112 4.3.3　輪盤(pán)比賽　113 4.4　可能性的倒塌　115 4.4.1　概率的定義　115 4.4.2　概率的意義　118 4.4.3　數(shù)學(xué)的應(yīng)用　118 4.4.4　解答疑問(wèn)　120 4.5　可能性的公理定義　121 4.5.1　柯?tīng)柲�哥洛夫�?21 4.5.2　樣本空間與概率分布函數(shù)　121 4.5.3　概率公理　125 4.5.4　子集與事件　126 4.5.5　概率公理P1　129 4.5.6　概率公理P2　130 4　目錄 4.5.7　概率公理P3　131 4.5.8　還沒(méi)有明白　132 4.5.9　擲出的點(diǎn)數(shù)為偶數(shù)的概率　134 4.5.10　質(zhì)地不均勻的骰子和豎立的硬幣　137 4.5.11　約定　138 4.5.12　咳嗽　139 第5　章 期望　143 5.1　隨機(jī)變量　143 5.1.1　媽媽　143 5.1.2　泰朵拉　144 5.1.3　隨機(jī)變量的示例　146 5.1.4　概率分布函數(shù)的示例　150 5.1.5　許多詞　152 5.1.6　期望　153 5.1.7　公平的游戲　157 5.2　線性法則　159 5.2.1　米爾嘉　159 5.2.2　和的期望等于期望的和　160 5.3　二項(xiàng)分布　165 5.3.1　硬幣的話題　165 5.3.2　二項(xiàng)分布的期望　168 5.3.3　劃分為和的形式　171 5.3.4　指示器隨機(jī)變量　172 5.3.5　快樂(lè)的作業(yè)　174 5.4　直到所有事情發(fā)生　175 目錄　5 5.4.1　不知何時(shí)　175 5.4.2　能盡全力嗎　176 5.4.3　運(yùn)用學(xué)到的知識(shí)　180 5.4.4　盡全力　183 5.4.5　意料之外的事情　192 第6　章 難以捉摸的未來(lái)　197 6.1　約定的記憶　197 6.2　階　199 6.2.1　更快的算法　199 6.2.2　至多為n階　201 6.2.3　出題　204 6.2.4　至多為f(n) 階　206 6.2.5　log n　211 6.3　查找　215 6.3.1　二分查找　215 6.3.2　實(shí)例　217 6.3.3　分析　220 6.3.4　前往排序　227 6.4　排序　228 6.4.1　冒泡排序　228 6.4.2　實(shí)例　229 6.4.3　分析　231 6.4.4　大O表示法的層級(jí)　235 6.5　動(dòng)態(tài)視角、靜態(tài)視角　237 6.5.1　需要比較多少次呢　237 6　目錄 6.5.2　比較樹(shù)　239 6.5.3　log n! 的評(píng)估　241 6.6　傳遞和學(xué)習(xí)　245 6.6.1　傳遞　245 6.6.2　學(xué)習(xí)　246 第7　章 矩陣　249 7.1　圖書(shū)室　249 7.1.1　瑞谷老師　249 7.1.2　TETRALIANE　250 7.2　尤里　252 7.2.1　無(wú)解　252 7.2.2　無(wú)窮多解　254 7.2.3　唯一解　256 7.2.4　信　268 7.3　泰朵拉　269 7.3.1　圖書(shū)室　269 7.3.2　行與列　269 7.3.3　矩陣與向量的積　271 7.3.4　聯(lián)立方程式與矩陣　273 7.3.5　矩陣的積　274 7.3.6　逆矩陣　275 7.4　米爾嘉　280 7.4.1　看穿隱藏的謎題　280 7.4.2　線性變換　286 7.4.3　旋轉(zhuǎn)　293 目錄　7 7.5　回家路上　296 第8　章 孤零零的隨機(jī)漫步　301 8.1　家　301 8.1.1　雨天的周六　301 8.1.2　下午茶時(shí)間　302 8.1.3　鋼琴問(wèn)題　302 8.1.4　旋律示例　305 8.1.5　解題方法一：毅力比拼　308 8.1.6　解題方法二：一招定勝負(fù)　310 8.1.7　一般化　314 8.1.8　搖擺不定的心　319 8.2　清晨的上學(xué)路　320 8.3　中午的教室　322 8.3.1　矩陣的練習(xí)　322 8.3.2　搖擺不定的心　325 8.4　放學(xué)后的圖書(shū)室　327 8.4.1　流浪問(wèn)題　327 8.4.2　A2 的意義　331 8.4.3　向著矩陣的n次方前進(jìn)　332 8.4.4　上半場(chǎng)準(zhǔn)備：對(duì)角矩陣　333 8.4.5　下半場(chǎng)準(zhǔn)備：矩陣與逆矩陣的三明治　335 8.4.6　向著特征值前進(jìn)　336 8.4.7　向著特征向量前進(jìn)　342 8.4.8　求An　344 8.5　家　347 8　目錄 8.5.1　搖擺不定的心　347 8.5.2　雨夜　349 第9　章 堅(jiān)強(qiáng)、正直、美麗　351 9.1　家　351 9.2　圖書(shū)室　358 9.2.1　邏輯題　358 9.2.2　可滿足性問(wèn)題　358 9.2.3　3-SAT　360 9.2.4　滿足　363 9.2.5　分配方式的練習(xí)　364 9.2.6　NP完全問(wèn)題　365 9.3　回家路上　367 9.3.1　誓言與約定　367 9.3.2　會(huì)議　368 9.4　圖書(shū)室　369 9.4.1　求解3-SAT問(wèn)題的隨機(jī)算法　369 9.4.2　隨機(jī)漫步　371 9.4.3　向著定量評(píng)估前進(jìn)　376 9.4.4　另一個(gè)隨機(jī)漫步　378 9.4.5　關(guān)注循環(huán)　379 9.5　家　384 9.5.1　幸運(yùn)的評(píng)估　384 9.5.2　化簡(jiǎn)和式　388 9.5.3　次數(shù)的評(píng)估　390 9.6　圖書(shū)室　391 目錄　9 9.6.1　獨(dú)立與互斥　391 9.6.2　精確的評(píng)估　392 9.6.3　斯特林公式　396 9.7　回家路上　403 9.8　家　405 第　10章 隨機(jī)算法　407 10.1　休閑餐廳　407 10.2　學(xué)校　409 10.2.1　中午　409 10.2.2　快速排序算法　410 10.2.3　通過(guò)樞紐項(xiàng)劃分?jǐn)?shù)列—兩只翅膀　413 10.2.4　對(duì)子數(shù)列排序—遞歸　417 10.2.5　運(yùn)行步數(shù)的分析　418 10.2.6　分情況討論　421 10.2.7　最大運(yùn)行步數(shù)　425 10.2.8　平均運(yùn)行步數(shù)　429 10.2.9　回家路上　434 10.3　自己家　435 10.3.1　變形　435 10.3.2　Hn 與log n　441 10.4　圖書(shū)室　443 10.4.1　米爾嘉　443 10.4.2　隨機(jī)快速排序　444 10.4.3　觀察比較過(guò)程　447 10.4.4　期望的線性法則　452 10　目錄 10.4.5　指示器隨機(jī)變量的期望等于概率　453 10.5　休閑餐廳　456 10.5.1　各種各樣的隨機(jī)算法　456 10.5.2　準(zhǔn)備　457 10.6　雙倉(cāng)圖書(shū)館　458 10.6.1　Iodine　458 10.6.2　緊張　459 10.6.3　報(bào)告　461 10.6.4　傳達(dá)　462 10.6.5　Oxygen　464 10.6.6　連接　465 10.6.7　庭園　466 10.6.8　約定的印記　468 尾　聲　471 后　記　477 參考文獻(xiàn)和導(dǎo)讀　481