漸進記法詳解

漸進記法有三種表示：
1.大O記法：T(n)=O(f(n))表示存在常數c>0,n₀>0,使得當n>=n0時，有T(n)<=cf(n)。
2.Ω記法：T(n)=Ω(f(n))表示存在常數c>0,n₀>0,使得當n>=n0時，有T(n)>=cf(n)。
3.Q記法：Q(f(n))表示同時有T(n)=O(f(n))和T(n)=Ω(f(n))。

說明：
對于法大O記法，在n為無窮大時，f(n)是T(n)的某種上界（一般指最小上界），而Ω記法是指f(n)是T(n)的某種下界（一般指最大下界），而Q記法則是指兩者同時成立，等價。

分析竅門
1.若T(n)是關于n的k階多項式，T(n)=Q(n^k)。
2.for循環時間復雜度等于循環次數乘以循環體代碼復雜度
3.對于if-else循環，復雜度判斷包括if語句的條件判斷，if代碼塊和else代碼塊，取最大的作為復雜度

關于復雜度的一些圖表
當輸入規模相同時，不同的復雜度需要的步數

對于不同的n，不同時間復雜度運行的時間對比

采用曲線的方式對比，更為直觀

總結

以上是生活随笔為你收集整理的数据结构：渐进记法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。