清華大學學堂在線 ?鄧俊輝老師 deng@tsinghua.edu.cn
第1章 緒論
(a)計算
計算=信息處理
對象：規(guī)律怔蚌，技巧 ? ? 目標：高效巩步，低耗
何為計算：借助某種工具，遵照一定規(guī)則桦踊，以明確而機械的形式進行椅野。
計算模型=計算機=信息處理工具
算法：
輸入：待處理的信息（問題）
輸出：經(jīng)處理的信息（答案）
正確性：的確可以解決指定的問題
確定性：任一算法都可以描述為一個有基本操作組成的序列
可行性：每一基本操作都可實現(xiàn)，且在常數(shù)時間內(nèi)完成
有窮性：對于任何輸入籍胯，經(jīng)有窮次基本操作都可以得到輸出
什么是個好算法：正確竟闪，健壯，可讀杖狼，
效率
Data Structure + Algorithms = Programs
(b)計算模型
成本：運行時間+存儲空間
特定算法+不同實例炼蛤， 以及，不同算法+特定實例
圖靈機 Turing Machine
包括：紙帶蝶涩，讀寫頭理朋，Transition Function
(q,c,d,L/R,p) 表示若當前狀態(tài)為q且當前字符為c，則將當前字符改寫為d绿聘，轉向左側/右側的鄰格嗽上，轉入p狀態(tài)，一旦轉入特定的終止狀態(tài) ‘h’ 熄攘，則停機兽愤。
在這些算法中，算法的運行時間成正比于算法需要執(zhí)行的基本操作次數(shù)。
執(zhí)行過程可以記錄為一張表浅萧，表的行數(shù)即是所執(zhí)行的基本指令的總條數(shù)逐沙，能夠客觀度量算法的執(zhí)行時間。
圖靈機(TM)洼畅，RAM等模型為度量算法性能提供了準確的尺度酱吝。
(c)大O記號(Big O Notation) ?Paul Bachmann 1894 ?同階無窮小
Mathematics is more in need of good notations than of new theorems. ----Alan Turing
長遠，主流
漸進分析 Asymptotic analysis:
當n>>2后土思，對于規(guī)模為n輸入务热，
算法需執(zhí)行的基本操作次數(shù)：T(n)=?? ? 需占用的存儲單元數(shù)：S(n)=??
T(n) = O(f(n)) ?iff ?存在 c>0，當 n>>2 后己儒，有 T(n) < c*f(n) 挨决。
O(1)：常數(shù)復雜度遵绰，2=2017=...=2011111111=O(1)
O( (log n)c ),對數(shù)多項式的復雜度 ?(poly log function)
對數(shù)：O(log n) ? ? ?ln n, lg n, ... , ?與對數(shù)的底數(shù)無關
常底數(shù)無所謂： 對任意的a，b，有 log(a)n=log(a)b*log(b)n=O( log(b)n )
常數(shù)次冪無所謂：對任意的c>0, (log n)c=c*log n=O(log n)
對于對數(shù)多項式而言希痴，取對數(shù)多項式里面次數(shù)最高的項即可
此類算法非常有效瓤湘，因為復雜度無限接近于常數(shù)壹甥。
對任意的c>0, n充分大時佛寿，O(log n)小于n的c次方。
O(n的c次方)何暇，多項式復雜度陶夜，polynomial function
O(2的n次方)，指數(shù)(exponential function) 指數(shù)爆炸
這類算法的計算成本增長極快裆站，通常被認為是不可忍受的条辟，從O(n的c次方)到O(2的n次方)，
是從有效算法到無效算法的分水嶺宏胯，很多問題的O(2的n次方)算法顯而易見羽嫡，
然而，設計出O(n的c次方)算法卻極為不易肩袍，甚至杭棵，有時注定地只能是徒勞無功。
對于2-Subset 問題魂爪，
直覺算法：逐一枚舉S集中的每一個子集，并統(tǒng)計其中元素的總和鹰祸，須2的n次方輪甫窟。
亦即：在最壞的情況下密浑，必須花費2的n次方的時間蛙婴，不甚理想！
直覺提出的問題：是否有更好的算法尔破？
定理：2-Subset is NP-complete
not Polynomial, 非多項式時間內(nèi)完成
即：就目前的計算模型而言街图，不存在可以在多項式時間內(nèi)回答此問題的算法浇衬，就此意義而言
上述的直覺算法已經(jīng)屬于最優(yōu)。
