說明：該系列博客整理自《算法導(dǎo)論(原書第二版)》，但更偏重于實(shí)用，所以晦澀偏理論的內(nèi)容未整理，請(qǐng)見諒。另外本人能力有限，如有問題，懇請(qǐng)指正！
1、漸近符號(hào)
????當(dāng)輸入規(guī)模大到使運(yùn)行時(shí)間只和增長(zhǎng)的量級(jí)有關(guān)時(shí)，就是在研究算法的?漸近?效率。就是說，從極限角度看，我們只關(guān)心算法運(yùn)行時(shí)間如何隨著輸入規(guī)模的無限增長(zhǎng)而增長(zhǎng)。通常，對(duì)不是很小的輸入規(guī)模而言，從漸近意義上說更有效的算法是最佳的選擇。
表示算法的漸近運(yùn)行時(shí)間的記號(hào)是用定義域?yàn)樽匀粩?shù)集?N?= {0， 1， 2， …} 的函數(shù)來定義的。這些記號(hào)便于用來表示最壞情況運(yùn)行時(shí)間?T?(?n?)。這些記號(hào)的定義域可以很容易地?cái)U(kuò)充至實(shí)數(shù)域或縮小到自然數(shù)的某個(gè)受限子集上，但要注意搞清楚這些表示法的準(zhǔn)確含義，方能做到越規(guī)使用而不誤用。
? ? 1.1、Θ?記號(hào)：表示漸近值，即真實(shí)值在漸近值的基礎(chǔ)上波動(dòng)
????????對(duì)一個(gè)給定的函數(shù)?g?(?n?)，用?Θ?(?g?(?n?))來表示函數(shù)集合：
????????對(duì)任何一個(gè)函數(shù)?f?(?n?)，若存在正常數(shù)?c1?，?c2?，使當(dāng)?n?充分大時(shí)，?f?(?n?)能被夾在?c1?g?(?n?)和?c2?g?(?n?)之間，則?f?(?n?)屬于集合?Θ?(?g?(?n?))?？梢詫懗伞?f?(?n?) ∈?Θ?(?g?(?n?))”表示?f?(?n?)是?Θ?(?g?(?n?))的元素。不過，通常寫成“?f?(?n?) =?Θ?(?g?(?n?))”來表示相同的意思。
????????上圖給出了函數(shù)?f?(?n?)和?g?(?n?)的直觀圖示，其中?f?(?n?) =?Θ?(?g?(?n?))。對(duì)所有位于?n0?右邊的?n?值，?f?(?n?)的值落在?c1?g?(?n?)和?c2?g?(?n?)之間。換句話說，對(duì)所有的?n?>=?n0?，?f?(?n?)在一個(gè)常數(shù)因子范圍內(nèi)與?g?(?n?)相等。我們說?g?(?n?)是?f?(?n?)的一個(gè)?漸近確界?。
? ??????Θ?(?g?(?n?))的定義要求每個(gè)成員?f?(?n?) ∈?Θ?(?g?(?n?))都是?漸近非負(fù)?，就是說當(dāng)?n?足夠大時(shí)?f?(?n?)是非負(fù)值。這就要求函數(shù)?g?(?n?)本身也是漸近非負(fù)的，否則集合?Θ?(?g?(?n?))就是空集。
? ??????Θ?記號(hào)表示漸近值，效果相當(dāng)于舍棄了低階項(xiàng)和忽略了最高階項(xiàng)的系數(shù)，即真實(shí)值在漸近值的基礎(chǔ)上波動(dòng)。
? ? 1.2、O?符號(hào)：表示上界
? ??????Θ?記號(hào)表示漸近值。當(dāng)只有?漸近?上界時(shí)，使用?O?記號(hào)。對(duì)一個(gè)函數(shù)?g?(?n?)，用?O?(?g?(?n?))表示一個(gè)函數(shù)集合：
????????上圖說明了?O?記號(hào)的直觀意義。對(duì)所有位于?n0?右邊的?n?值，函數(shù)?f?(?n?)的值在?g?(?n?)下。
? ? 1.3、Ω?記號(hào)：表示下界
? ??????Ω?記號(hào)給出了函數(shù)的漸近下界。給定一個(gè)函數(shù)?g?(?n?)，用?Ω?(?g?(?n?))表示一個(gè)函數(shù)集合：
????????上圖說明了?Ω?記號(hào)的直觀意義。對(duì)所有在?n0?右邊的?n?值，函數(shù)?f?(?n?)的數(shù)值等于或大于?c g?(?n?)。
? ??????定理
????????????對(duì)任意兩個(gè)函數(shù)?f?(?n?)和?g?(?n?)，?f?(?n?) =?Θ?(?g?(?n?))當(dāng)且僅當(dāng)?f?(?n?) =?O?(?g(n))和?f?(?n?) =?Ω?(?g?(?n?))。
? ? 1.4、o?記號(hào)
? ??????O?記號(hào)提供的漸近上界可能是也可能不是漸近緊確的。這里用?o?記號(hào)表示非漸近緊確的上界。?o?(?g?(?n?))的形式定義為集合：
? ??????O?記號(hào)與?o?記號(hào)的主要區(qū)別在于對(duì)?f?(?n?) =?O?(?g?(?n?))，界0 <=?f?(?n?) <=?c g?(?n?)對(duì)某個(gè)常數(shù)?c?> 0成立；但對(duì)?f?(?n?) =?o?(?g?(?n?))，界0 <=?f?(?n?) <=?c g?(?n?)對(duì)所有常數(shù)?c?> 0都成立。即
? ? 1.5、ω?記號(hào)
????????我們用?ω?記號(hào)來表示非漸近緊確的下界。?ω?(?g?(?n?))的形式定義為集合：
????????關(guān)系?f?(?n?) =?ω?(?g?(?n?))意味著
????????如果這個(gè)極限存在。也就是說當(dāng)?n?趨于無窮時(shí)，?f?(?n?)相對(duì)?g?(?n?)來說變得任意大了。
2、算法中常見函數(shù)介紹
? ? 暫未整理
3、參考文檔
? ??算法導(dǎo)論讀書筆記(3)
