演算法導論第二課——漸進分析

本文給出幾種標準方法來簡化演算法的漸進分析，首先定義幾類漸進符號，其中演算法導論第一課中的 notation。

notation表示漸進上界

表示函數具有漸進上界，對於給定的函數 ，用 來表示以下函數的集合：

例如 ，這裡的 並不是傳統的等於的意思，而是 的意思，即

當我們說運行時間為 時，指存在一個屬於 的函數 使得對 的任意值，不管選擇什麼規模為n的輸入，其運行時間的上界都是 ，也就是說最壞情況運行時間為 .

notation 表示漸進緊確界

對於一個給定的函數 ，用 來表示以下函數的集合：

若存在正常量 使得對於足夠大的 ，函數 能夠夾入 和 之間，則 屬於集合 ，即 ，我們用 來表示同樣的概念。

在演算法導論第一課中我們介紹了 符號的非形式化的概念，相當於扔掉低階項並忽略最高階項前的係數，我們來使用形式化定義來證明

按照定義我們必須確定正常量 來使得對所有的 有：

即得到：

取 , , ，即可得到

從上述例子可以看出，常量選擇依賴於函數本身，屬於 的不同函數通常需要不同的常量。

一般來說，對於任意多項式pn ，其中 為常量且 ，我們有 .

notation 表示漸進下界

對於給定的函數 ,用 來表示以下函數的集合：

定理：對於任意的兩個函數 ，我們有 ，當且僅當 且