Big-O記法

一般用O（n）記法來(lái)漸進(jìn)界定算法運(yùn)行時(shí)間的常數(shù)函數(shù)邊界。希望這個(gè)常數(shù)函數(shù)代表算法運(yùn)行時(shí)間的上界。

在最差情況下二分法搜索的運(yùn)行時(shí)間為O（lgn），認(rèn)為在所有情況下二分法搜索的搜索時(shí)間為O（lgn）是錯(cuò)誤的。

二分法搜索的時(shí)間從來(lái)不會(huì)超過(guò)O（lgn），多數(shù)情況下其搜索時(shí)間都會(huì)少于O（lgn）

一般算法中基本操作重復(fù)執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T（n）表示，若有個(gè)輔助函數(shù)f（n）是T（n）的同數(shù)量級(jí)函數(shù)。記作T（n）=O（f（n）），即為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度

T（n）=O（f（n））表示存在一個(gè)常數(shù)C，使得在n趨于無(wú)窮時(shí)總有T（n）<=C*f（n）。

Big-Theta記法

當(dāng)n變得很大的時(shí)候，算法的運(yùn)行時(shí)間介于k1?n和k2?n之間，其中k1和k2為常數(shù)

Big-Omega記法

有的算法只能描述其至少要運(yùn)行多少時(shí)間而無(wú)法給出其運(yùn)行時(shí)間的上限時(shí)使用，存在足夠大的n，運(yùn)行時(shí)間至少是k?f（n），其中k為常數(shù)。