清華大學(xué)學(xué)堂在線 ?鄧俊輝老師 deng@tsinghua.edu.cn
第1章 緒論
(a)計(jì)算
計(jì)算=信息處理
對(duì)象：規(guī)律，技巧 ? ? 目標(biāo)：高效，低耗
何為計(jì)算：借助某種工具，遵照一定規(guī)則，以明確而機(jī)械的形式進(jìn)行。
計(jì)算模型=計(jì)算機(jī)=信息處理工具
算法：
輸入：待處理的信息（問題）
輸出：經(jīng)處理的信息（答案）
正確性：的確可以解決指定的問題
確定性：任一算法都可以描述為一個(gè)有基本操作組成的序列
可行性：每一基本操作都可實(shí)現(xiàn)，且在常數(shù)時(shí)間內(nèi)完成
有窮性：對(duì)于任何輸入，經(jīng)有窮次基本操作都可以得到輸出
什么是個(gè)好算法：正確，健壯，可讀，
效率
Data Structure + Algorithms = Programs
(b)計(jì)算模型
成本：運(yùn)行時(shí)間+存儲(chǔ)空間
特定算法+不同實(shí)例， 以及，不同算法+特定實(shí)例
圖靈機(jī) Turing Machine
包括：紙帶，讀寫頭，Transition Function
(q,c,d,L/R,p) 表示若當(dāng)前狀態(tài)為q且當(dāng)前字符為c，則將當(dāng)前字符改寫為d，轉(zhuǎn)向左側(cè)/右側(cè)的鄰格，轉(zhuǎn)入p狀態(tài)，一旦轉(zhuǎn)入特定的終止?fàn)顟B(tài) ‘h’ ，則停機(jī)。
在這些算法中，算法的運(yùn)行時(shí)間成正比于算法需要執(zhí)行的基本操作次數(shù)。
執(zhí)行過程可以記錄為一張表，表的行數(shù)即是所執(zhí)行的基本指令的總條數(shù)，能夠客觀度量算法的執(zhí)行時(shí)間。
圖靈機(jī)(TM)，RAM等模型為度量算法性能提供了準(zhǔn)確的尺度。
(c)大O記號(hào)(Big O Notation) ?Paul Bachmann 1894 ?同階無窮小
Mathematics is more in need of good notations than of new theorems. ----Alan Turing
長(zhǎng)遠(yuǎn)，主流
漸進(jìn)分析 Asymptotic analysis:
當(dāng)n>>2后，對(duì)于規(guī)模為n輸入，
算法需執(zhí)行的基本操作次數(shù)：T(n)=?? ? 需占用的存儲(chǔ)單元數(shù)：S(n)=??
T(n) = O(f(n)) ?iff ?存在 c>0，當(dāng) n>>2 后，有 T(n) < c*f(n) 。
O(1)：常數(shù)復(fù)雜度，2=2017=...=2011111111=O(1)
O( (log n)c ),對(duì)數(shù)多項(xiàng)式的復(fù)雜度 ?(poly log function)
對(duì)數(shù)：O(log n) ? ? ?ln n, lg n, ... , ?與對(duì)數(shù)的底數(shù)無關(guān)
常底數(shù)無所謂： 對(duì)任意的a，b，有 log(a)n=log(a)b*log(b)n=O( log(b)n )
常數(shù)次冪無所謂：對(duì)任意的c>0, (log n)c=c*log n=O(log n)
對(duì)于對(duì)數(shù)多項(xiàng)式而言，取對(duì)數(shù)多項(xiàng)式里面次數(shù)最高的項(xiàng)即可
此類算法非常有效，因?yàn)閺?fù)雜度無限接近于常數(shù)。
對(duì)任意的c>0, n充分大時(shí)，O(log n)小于n的c次方。
O(n的c次方)，多項(xiàng)式復(fù)雜度，polynomial function
O(2的n次方)，指數(shù)(exponential function) 指數(shù)爆炸
這類算法的計(jì)算成本增長(zhǎng)極快，通常被認(rèn)為是不可忍受的，從O(n的c次方)到O(2的n次方)，
是從有效算法到無效算法的分水嶺，很多問題的O(2的n次方)算法顯而易見，
然而，設(shè)計(jì)出O(n的c次方)算法卻極為不易，甚至，有時(shí)注定地只能是徒勞無功。
對(duì)于2-Subset 問題，
直覺算法：逐一枚舉S集中的每一個(gè)子集，并統(tǒng)計(jì)其中元素的總和，須2的n次方輪。
亦即：在最壞的情況下，必須花費(fèi)2的n次方的時(shí)間，不甚理想！
直覺提出的問題：是否有更好的算法？
定理：2-Subset is NP-complete
not Polynomial, 非多項(xiàng)式時(shí)間內(nèi)完成
即：就目前的計(jì)算模型而言，不存在可以在多項(xiàng)式時(shí)間內(nèi)回答此問題的算法，就此意義而言
上述的直覺算法已經(jīng)屬于最優(yōu)。
