一、時間復雜度BigO

首先我們不能以機器運行算法的時間來評判一個算法的時間復雜度，因為即使是相同的算法在不同機器上（機器的個體差異性）運行時間都可能不盡相同，因此我們采用

(相關資料圖)

【大O表示法】——算法的漸進復雜度T（n）=O（f（n））。

首先解讀這個公式，f（n）表示代碼執行的次數，O表示正比例關系，而T（n）就表示算法的漸進復雜度（就是當一個問題量級增加的時候，算法運行時間增長的一個趨勢）。

例題辨析

for(int i=1;i<=n;i++){  x++;}

請問這個代碼塊執行幾次？

答：3N+1次

解析：

首先開頭定義i=1，執行一次，后面在循環中就不參與，而i<=n,x++,i++各執行N次，所以相加就是3N+1次。

O（3N+1）=O（N），因為這個公式計算的是當n無限接近于正無窮時，可以省略1和3.

上面的代碼執行N^2次

上面的代碼原則上是執行N+N^2次，而又因為N是趨近于無窮的，所以最終結果就是N^2次，即O（N+N^2）=O(N^2)！

常用的時間復雜度量級

橫坐標表示代碼執行的次數，縱坐標表示時間復雜度量級。

從圖中不難看出，n!、2^n\、n2時間復雜度都是指數級的，因此代碼運行的非常慢。

1、O(1)

上面代碼時間復雜度是O（1），因為當其中變量的值增加到任何值，本質交換兩個數的值，時間復雜度就是O（1）

2、O（n）

這時復雜度就取決于n的大小

3、O（log n）

這其實是一道數學題，就是2^k=n,求k

兩邊同取對數，答案即為log n（注意此時的底數都可以忽略不計）

4、O（nlog n）

比較容易理解，外面套了一層循環，就是在原來的基礎上*n。

5、o（m*n）

就是for循環嵌套，俗稱套娃。

二、空間復雜度

空間復雜度自然也不是計算空間的大小，而是內存空間增長的趨勢。

常用的空間復雜度

O（1）、O（n）、O（n^2）

1、O（1）

無論xy增加到多少，內存分配還是不變，因此還是O（1）

2、O（n）

隨著n的增加，對數組分配的空間也增多

三、總結

時間空間復雜度=時間和空間增長的復雜度