計(jì)算的復(fù)雜度是一個(gè)特定算法在運(yùn)行時(shí)所消耗的計(jì)算資源(時(shí)間和空間)的度量。

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

1、時(shí)間復(fù)雜度

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

2、空間復(fù)雜度

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

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

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

1、線性回歸

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

2、邏輯回歸：

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

3、支持向量機(jī)：

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

4、樸素貝葉斯：

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

5、決策樹：

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

6、隨機(jī)森林：

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

7、K近鄰：

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

Brute：

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

kd-tree：

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

8、K-means 聚類：

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