在表示算法的時(shí)間復(fù)雜度上 囤锉， 我們通常會(huì)使用漸進(jìn)符號(hào)
常用的漸進(jìn)符號(hào)有 ：O ，Ω ，θ
那么這三個(gè)符號(hào)分別表示了什么含義呢
O( f(n) ) : 給出了算法運(yùn)行時(shí)間的上界 ， 也就是最壞情況下的時(shí)間復(fù)雜度
Ω( f(n) ) : 給出了算法運(yùn)行時(shí)間的下界 聘殖， 也就是最好情況下的時(shí)間復(fù)雜度
θ ( f(n) ) : 給出了算法運(yùn)行時(shí)間的上界和下界 ， 這里 θ ( f(n) ) 是漸進(jìn)的確界
首先 ， 這三個(gè)符號(hào) 奸腺， 并不一定都和算法分析有關(guān) 餐禁， 這三個(gè)符號(hào)只是用來刻畫函數(shù)的增長速度的 ， 假如有函數(shù) ： f(n) = 3n^2 + 100n + 1000突照， 那么我們就可以說 f(n) = O(n^2) = O(n^3) , f(n) = Ω(n^2) = Ω(n) , f(n) = θ(n^2) 帮非。
當(dāng)具體到算法復(fù)雜度分析上，比如說插入排序讹蘑。在最壞的情況下(原序列是倒序) ,如果我們仔細(xì)計(jì)算此時(shí)需要的比較和交換次數(shù) , 會(huì)發(fā)現(xiàn)它是一個(gè) f(n)=An^2+..的形式 , 于是我們可以說:
插入排序在最壞情況下的時(shí)間復(fù)雜度是:θ(n^2) , 也是O(n^2) ,也是Ω(n^2) 末盔。
在最好的情況下(原序列已經(jīng)有序)的時(shí)間復(fù)雜度是 ： θ(n) ， O(n) 衔肢，也是Ω(n) 庄岖。
如果在非特定條件下 ，插入排序(在所有情況下)的時(shí)間復(fù)雜度是多少呢 角骤？ 這個(gè)時(shí)候就不能使用θ來回答了 ， 因?yàn)?strong>最好情況和最壞情況的θ是不同的 心剥， 所以我們只能說 邦尊，在所有情況下它的時(shí)間復(fù)雜度都是O(n^2) ，也可以回答 优烧， 在所有的情況下都是Ω(n)蝉揍；
