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

計算復(fù)雜度又分為兩類:

1、時間復(fù)雜度

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

2、空間復(fù)雜度

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

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

下面我們整理了一些常見的機器學(xué)習(xí)算法的計算復(fù)雜度。

1、線性回歸

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

2、邏輯回歸：

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

3、支持向量機：

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

4、樸素貝葉斯：

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

5、決策樹：

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

6、隨機森林：

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

7、K近鄰：

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

Brute：

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

kd-tree：

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

8、K-means 聚類：

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