目錄

一 、 大 O 記法?

二、Ω 記法。

三、 Θ記法

四、小o記法

五、命中緩存對時間效率的影響。

六、主定理

---

時間復雜度反應了一個程序的運行時間關于實例個數變化而變化規律。在一個排序程序中，可能比較了 2n 次，但是執行步數可能達到了 2n^3 ，就不能直接判定程序運行時間是 n 的線性函數。兩個程序比較次數一個是3n，一個是2n 那么不能說前者的花費的時間就要更慢些，因為在總的執行步數上未必會比后者多。

當實例個數足夠多的時候，計量時間的方法叫做漸進記法，最常用的是 O(g(x)) 表示。其他常用還有 o? ， Ω ， Θ 記法。

一 、 大 O 記法?

當實例個數n足夠多時 ，程序執行總步數 f(n) = O(g(n)) 時滿足 ：

? ?? ??

例如 當 程序執行步數為? f(n)= n^2+ 4log2?n? ? ?那么? f(n) = O(n^2) 成立， f(n) = O(n^3) 也成立。

二、Ω 記法。

當實例個數n足夠多時 ，程序執行總步數 f(n) = Ω(g(n)) 時滿足 ：

? ?? 其中C為常數。

? ??例如 當 程序執行步數為? f(n)= n^2+ 4log2?n? ? ?那么? f(n) = Ω(n^2) 成立， f(n) = Ω(n) 也成立。 f(n) = Ω(n^3) 不成立

三、 Θ記法

當實例個數n足夠多時 ，程序執行總步數 f(n) = Θ(g(n)) 時滿足 ：

? ?? 其中C為常數。

?例如 當 程序執行步數為? f(n)= n^2+ 4log2?n? ? ?那么? f(n) = Θ(n^2) 成立， f(n) = Θ(n) 不成立。 f(n) = Θ(n^3) 不成立

四、小o記法

當實例個數n足夠多時 ，程序執行總步數 f(n) = o(g(n)) 時滿足 ：

當且僅當? ? ? f(n) =O(g(n)) 且?? f(n) 不等于 Ω (g(n)) 時 即?

?例如 當 程序執行步數為? f(n)= n^2+ 4log2?n? ? ?那么? f(n) = o(n^2) 不成立， f(n) = o(n) 成立。 f(n) = o(n^3) 不成立

五、命中緩存對時間效率的影響。

在簡單的計算機模型中，它的存儲由1級緩存，二級緩存和主存構成。算術和邏輯操作由算術和邏輯單元 （ALU） 對存儲在寄存器R中的數據進行處理來完成。通常主存的大小時幾百MB，二級緩存大小不足1MB，1級緩存的大小是幾十KB，寄存器的數量在8到32之間。容量越小的，讀取效率越高。

程序在運行時，所有數據都在主存，當要讀取數據時，程序會率先在1級緩存中去找，如果沒有再去二級緩存去找，之后再去主存中去找，在緩存中讀取的需要數據比起在主存中讀取需要的數據效率來得高。如果在主存中找到需要的數據，會把它復制到在二級緩存，一級緩存和寄存器中，再進行操作。

因為緩存的存在，時程序相同執行步數的情況下，耗時也可能會大有不同。

例如有二維數組即矩陣的乘法運算

//程序1 i j k 的遍歷方式 void multiplyMartix(int **a , int ** b ,int **c,int n){//初始化矩陣c 的值為 0 initial(c,0);for (int i =0 ; i< n ;i++)for (int j =0 ; j< n ;k++)for (int k =0 ; k< n ;k++)c[i][j] += a[i][k] * b[k][j]; }//效率的更高的程序二 i k j 的遍歷方式 void multiplyMartix(int **a , int ** b ,int **c,int n){//初始化矩陣c 的值為 0 initial(c,0);for (int i =0 ; i< n ;i++)for (int k =0 ; k< n ;k++)for (int j =0 ; j< n ;k++)c[i][j] += a[i][k] * b[k][j]; }

由與第二個程序，再1次內部第3層循環中，每一次循環讀的 a[i][k] 的臨時變量都是同一個，所以緩存命中次數要比第1個程序占比來得高，效率更快。

六、主定理

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的时间复杂度、渐进记法、主定理的全部內容，希望文章能夠幫你解決所遇到的問題。

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