計算的復雜度是一個特定算法在運行時所消耗的計算資源(時間和空間)的度量。

計算復雜度又分為兩類:

1、時間復雜度

時間復雜度不是測量一個算法或一段代碼在某個機器或者條件下運行所花費的時間。時間復雜度一般指時間復雜性，時間復雜度是一個函數(shù)，它定性描述該算法的運行時間，允許我們在不運行它們的情況下比較不同的算法。例如，帶有O(n)的算法總是比O(n2)表現(xiàn)得更好，因為它的增長率小于O(n2)。

2、空間復雜度

就像時間復雜度是一個函數(shù)一樣，空間復雜度也是如此。 從概念上講，它與時間復雜度相同，只需將時間替換為空間即可。 維基百科將空間復雜度定義為：

算法或計算機程序的空間復雜度是解決計算問題實例所需的存儲空間量，以特征數(shù)量作為輸入的函數(shù)。

下面我們整理了一些常見的機器學習算法的計算復雜度。

1、線性回歸

• n= 訓練樣本數(shù)，f = 特征數(shù)
• 訓練時間復雜度：O(f2n+f3)
• 預測時間復雜度：O(f)
• 運行時空間復雜度：O(f)

2、邏輯回歸：

• n= 訓練樣本數(shù)，f = 特征數(shù)
• 訓練時間復雜度：O(f*n)
• 預測時間復雜度：O(f)
• 運行時空間復雜度：O(f)

3、支持向量機：

• n= 訓練樣本數(shù)，f = 特征數(shù)，s= 支持向量的數(shù)量
• 訓練時間復雜度：O(n2) 到 O(n3)，訓練時間復雜度因內核不同而不同。
• 預測時間復雜度：O(f) 到 O(s*f):線性核是 O(f)，RBF 和多項式是 O(s*f)
• 運行時空間復雜度：O(s)

4、樸素貝葉斯：

• n= 訓練樣本數(shù)，f = 特征數(shù)，c = 分類的類別數(shù)
• 訓練時間復雜度：O(n*f*c)
• 預測時間復雜度：O(c*f)
• 運行時空間復雜度：O(c*f)

5、決策樹：

• n= 訓練樣本數(shù)，f = 特征數(shù)，d = 樹的深度，p = 節(jié)點數(shù)
• 訓練時間復雜度：O(n*log(n)*f)
• 預測時間復雜度：O(d)
• 運行時空間復雜度：O(p)

6、隨機森林：

• n= 訓練樣本數(shù)，f = 特征數(shù)，k = 樹的數(shù)量，p=樹中的節(jié)點數(shù)，d = 樹的深度
• 訓練時間復雜度：O(n*log(n)*f*k)
• 預測時間復雜度：O(d*k)
• 運行時空間復雜度：O(p*k)

7、K近鄰：

n= 訓練樣本數(shù)，f = 特征數(shù)，k= 近鄰數(shù)

Brute：

• 訓練時間復雜度：O(1)
• 預測時間復雜度：O(n*f+k*f)
• 運行時空間復雜度：O(n*f)

kd-tree：

• 訓練時間復雜度：O(f*n*log(n))
• 預測時間復雜度：O(k*log(n))
• 運行時空間復雜度：O(n*f)

8、K-means 聚類：

• n= 訓練樣本數(shù)，f = 特征數(shù)，k= 簇數(shù)，i = 迭代次數(shù)
• 訓練時間復雜度：O(n*f*k*i)
• 運行時空間復雜度：O(n*f+k*f)