函數的增長

1：漸進記号

我們主要用漸進記号來描寫叙述算法的執行時間

Θ記号：如Θ（g(n)） 是函數的一個漸進緊确界

O記号：如O（g(n)） 是函數的一個漸進緊确上界

o記号：如o（g(n)）

是函數的一個漸進緊确上界

Ω記号：如Ω（g(n)）

是函數的一個漸進緊确下界

w記号：如w（g(n)）

漸進函數性質：

傳遞性：

f(n)=Ω（g(n)）且g(n)=Θ（h(n)）

蘊含f(n)=Θ（h(n)）

f(n)=O(g(n))

且g(n)=O(h(n)) 蘊含f(n)=O(h(n))

f(n)=Ω(g(n))

且g(n)=Ω(h(n)) 蘊含f(n)=Ω(h(n))

f(n)=o(g(n))

且g(n)=o(h(n)) 蘊含f(n)=o(h(n))

f(n)=w(g(n))

且g(n)=w(h(n)) 蘊含f(n)=w(h(n))

自反性：

f(n)=Θ(f(n))

f(n)=O(f(n))

f(n)=Ω(f(n))

對稱性：

f(n)=Θ(g(n))當且僅當g(n)=Θ(f(n))

轉置對稱性：

f(n)=O(g(n))當且僅當g(n)=Ω(f(n))

f(n)=o(g(n))當且僅當g(n)=w(f(n))

兩個函數f和g的漸進比較和兩個實數a和b比較之間做一種類比

f(n)=O(g(n)) 類似于a<=b

f(n)=o(g(n)) 類似于a<b

f(n)=Θ(g(n))類似于a=b

f(n)=Ω(g(n)) 類似于a>=b

類似于a>b

三分性 ：對随意兩個函數，a和b下列三種情況恰有一種必須成立 a<b ,a=b,或a>b

 可是漸進函數對此不成立：由于。有可能函數┗的值在中間來回擺動，而不是取唯一值

标準記号與經常使用函數：

單調性。向下取整，向上取整。模運算,指數，對數，階乘，多重函數，多重對數函數

模運算：對随意整數a 和随意整數n,a mod n的值就是上a  /n的餘數

                       a mod n = a - n└╁   a/n ┘

                         0<=a mod n <n