１．計(jì)算機(jī)與算法
１．排序
將n個(gè)整數(shù)按通常的大小次序排成一個(gè)非降序列。 這類(lèi)操作統(tǒng)稱(chēng)排序（sorting）．
從前向后依次檢查每一對(duì)相鄰元素，一旦發(fā)現(xiàn)逆序即交換二者的位置。對(duì)于長(zhǎng)度為n的序列，共需做n - 1次比較和不超過(guò)n - 1次交換，這一過(guò)程稱(chēng)作一趟掃描交換。需要反復(fù)進(jìn)行多次掃描交換，直到序列中不再含有任何逆序的相鄰元素。排序過(guò)程中， 所有元素朝各自最終位置亦步亦趨的移動(dòng)過(guò)程，猶如氣泡在水中的上下沉浮，起泡排序（bubblesort） 算法也因此得名。
２．算法
什么是算法呢？所謂算法，是指基于特定的計(jì)算模型，旨在解決某一信息處理問(wèn)題而設(shè)計(jì)的一個(gè)指令序列。算法應(yīng)必須具備以下要素：
輸入與輸出
基本操作、確定性與可行性
有窮性與正確性
：證明算法有窮性和正確性的一個(gè)重要技巧，就是從適當(dāng)?shù)慕嵌葘徱曊麄€(gè)計(jì)算過(guò)程，并找出其所具有的某種不變性和單調(diào)性。其中的單調(diào)性通常是指， 問(wèn)題的有效規(guī)模會(huì)隨著算法的推進(jìn)不斷遞減。不變性則不僅應(yīng)在算法初始狀態(tài)下自然滿(mǎn)足，而且應(yīng)與最終的正確性相呼應(yīng)－－當(dāng)問(wèn)題的有效規(guī)?？s減到0時(shí)，不變性應(yīng)隨即等價(jià)于正確性。
起泡排序算法的不變性和單調(diào)性可分別概括為： 經(jīng)過(guò)k趟掃描交換之后，最大的前k個(gè)元素必然就位；經(jīng)過(guò)k趟掃描交換之后，待求解問(wèn)題的有效規(guī)模將縮減至n - k。
3．要求
同一問(wèn)題往往不限于一種算法，而同一算法也常常會(huì)有多種實(shí)現(xiàn)方式，因此除了以上必須具備的基本屬性，在應(yīng)用環(huán)境中還需從實(shí)用的角度對(duì)不同算法及其不同版本做更為細(xì)致考量和取舍。如：
退化與魯棒性
退化（degeneracy） 情況：除一般性情況外，實(shí)用的算法還應(yīng)能夠處理各種極端的輸入實(shí)例。
魯棒性（robustness） ：就是要求能夠盡可能充分地應(yīng)對(duì)此類(lèi)情況。
重用性
另一標(biāo)準(zhǔn)是： 算法的總體框架能否便捷地推廣至其它場(chǎng)合。實(shí)際上，起泡算法的正確性與所處理序列中元素的類(lèi)型關(guān)系不大，無(wú)論是對(duì)于float、 char或其它類(lèi)型，只要元素之間可以比較大小，算法的整體框架就依然可以沿用。算法模式可推廣并適用于不同類(lèi)型基本元素的這種特性，即是重用性的一種典型形式。
４．算法效率
包括：可計(jì)算性（computability），難解性（intractability） ，計(jì)算效率：從時(shí)間和空間等方面度量算法的計(jì)算成本，數(shù)據(jù)結(jié)構(gòu)：要做到根據(jù)實(shí)際應(yīng)用需求自如地設(shè)計(jì)、實(shí)現(xiàn)和選用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，必須首先對(duì)算法設(shè)計(jì)的技巧以及相應(yīng)數(shù)據(jù)結(jié)構(gòu)的特性了然于心，這些也是本書(shū)的重點(diǎn)與難點(diǎn)。
２．復(fù)雜度度量
１．時(shí)間復(fù)雜度
隨著輸入規(guī)模的擴(kuò)大，算法的執(zhí)行時(shí)間將如何增長(zhǎng)？執(zhí)行時(shí)間的這一變化趨勢(shì)可表示為輸入規(guī)模的一個(gè)函數(shù)，稱(chēng)作該算法的時(shí)間復(fù)雜度（ time complexity）。具體地，特定算法處理規(guī)模為n的問(wèn)題所需的時(shí)間可記作T(n)。從保守估計(jì)的角度出發(fā)，在規(guī)模為n的所有輸入中選擇執(zhí)行時(shí)間最長(zhǎng)者作為T(mén)(n)， 并以T(n)度量該算法的時(shí)間復(fù)雜度。
小規(guī)模問(wèn)題所需的處理時(shí)間本來(lái)就相對(duì)更少， 故此時(shí)不同算法的實(shí)際效率差異并不明顯；而在處理更大規(guī)模的問(wèn)題時(shí)，效率的些許差異都將對(duì)實(shí)際執(zhí)行效果產(chǎn)生巨大的影響。著眼長(zhǎng)遠(yuǎn)、更為注重時(shí)間復(fù)雜度的總體變化趨勢(shì)和增長(zhǎng)速度的策略與方法，即所謂的漸進(jìn)分析（ asymptotic analysis）．
１．大O記號(hào)（worst case）
環(huán)境差異：
事實(shí)上，即便是同一算法、同一輸入，在不同的硬件平臺(tái)上、不同的操作系統(tǒng)中甚至不同的時(shí)間，所需要的計(jì)算時(shí)間都不盡相同。因此，有必要按照超脫于具體硬件平臺(tái)和軟件環(huán)境的某一客觀標(biāo)準(zhǔn)，來(lái)度量算法的時(shí)間復(fù)雜度， 并進(jìn)而評(píng)價(jià)不同算法的效率差異。
基本操作－不妨將T(n)定義為算法所執(zhí)行基本操作的總次數(shù)。
一種自然且可行的解決辦法是，將時(shí)間復(fù)雜度理解為算法中各條指令的執(zhí)行時(shí)間之和。在圖靈機(jī)（Turing Machine, TM） 和隨機(jī)存儲(chǔ)機(jī)（Random Access Machine, RAM） 等計(jì)算模型中， 指令語(yǔ)句均可分解為若干次基本操作，比如算術(shù)運(yùn)算、比較、分支、子程序調(diào)用與返回等；而在大多數(shù)實(shí)際的計(jì)算環(huán)境中，每一次這類(lèi)基本操作都可在常數(shù)時(shí)間內(nèi)完成。
也就是說(shuō)， T(n)決定于組成算法的所有語(yǔ)句各自的執(zhí)行次數(shù)，以及其中所含基本操作的數(shù)目。
例子：起泡排序問(wèn)題中，在每一輪內(nèi)循環(huán)中，需要掃描和比較n - 1對(duì)元素，至多需要交換n - 1對(duì)元素。元素的比較和交換， 都屬于基本操作，故每一輪內(nèi)循環(huán)至多需要執(zhí)行2(n - 1)次基本操作。外循環(huán)至多執(zhí)行n - 1輪。因此，總共需要執(zhí)行的基本操作不會(huì)超過(guò)2(n - 1)＾2次。
２．大Ω記號(hào)（ best case）
３．大\theta記號(hào)
４．三種記號(hào)的比較
２．空間復(fù)雜度
就漸進(jìn)復(fù)雜度的意義而言，在任一算法的任何一次運(yùn)行過(guò)程中所消耗的存儲(chǔ)空間， 都不會(huì)多于其間所執(zhí)行基本操作的累計(jì)次數(shù)。
實(shí)際上根據(jù)定義，每次基本操作所涉及的存儲(chǔ)空間， 都不會(huì)超過(guò)常數(shù)規(guī)模； 縱然每次基本操作所占用或訪(fǎng)問(wèn)的存儲(chǔ)空間都是新開(kāi)辟的，整個(gè)算法所需的空間總量， 也不過(guò)與基本操作的次數(shù)同階。從這個(gè)意義上說(shuō)，時(shí)間復(fù)雜度本身就是空間復(fù)雜度的一個(gè)天然的上界。
３．復(fù)雜度分析
１．常數(shù)O(1)
２．對(duì)數(shù)O(logn)
對(duì)數(shù)多項(xiàng)式復(fù)雜度
３．線(xiàn)性O(shè)(n)
? ? 多項(xiàng)式時(shí)間復(fù)雜度算法
４．指數(shù)O(２＾n)
復(fù)雜度層次
