8 個常見的機器學習算法的計算複雜度總結

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

計算複雜度又分爲兩類：

一、時間複雜度

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

二、空間複雜度

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

算法或計算機程序的空間複雜度是解決計算問題實例所需的存儲空間量，以特徵數量作爲輸入的函數。

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

1. 線性迴歸

n= 訓練樣本數，f = 特徵數

訓練時間複雜度：O(f²n+f³)

預測時間複雜度：O(f)

運行時空間複雜度：O(f)

2. 邏輯迴歸

n= 訓練樣本數，f = 特徵數

訓練時間複雜度：O(f*n)

預測時間複雜度：O(f)

運行時空間複雜度：O(f)

3. 支持向量機

n= 訓練樣本數，f = 特徵數，s= 支持向量的數量

訓練時間複雜度：O(n²) 到 O(n³)，訓練時間複雜度因內核不同而不同。

預測時間複雜度：O(f) 到 O(sf): 線性核是 O(f)，RBF 和多項式是 O(sf)

運行時空間複雜度：O(s)

4. 樸素貝葉斯

n= 訓練樣本數，f = 特徵數，c = 分類的類別數

訓練時間複雜度：O(nfc)

預測時間複雜度：O(c*f)

運行時空間複雜度：O(c*f)

5. 決策樹

n= 訓練樣本數，f = 特徵數，d = 樹的深度，p = 節點數

訓練時間複雜度：O(n*log(n)*f)

預測時間複雜度：O(d)

運行時空間複雜度：O(p)

6. 隨機森林

n= 訓練樣本數，f = 特徵數，k = 樹的數量，p = 樹中的節點數，d = 樹的深度

訓練時間複雜度：O(n*log(n)fk)

預測時間複雜度：O(d*k)

運行時空間複雜度：O(p*k)

7. K 近鄰

n= 訓練樣本數，f = 特徵數，k= 近鄰數

Brute：

訓練時間複雜度：O(1)

預測時間複雜度：O(nf+kf)

運行時空間複雜度：O(n*f)

kd-tree：

訓練時間複雜度：O(fnlog(n))

預測時間複雜度：O(k*log(n))

運行時空間複雜度：O(n*f)

8. K-means 聚類

n= 訓練樣本數，f = 特徵數，k= 簇數，i = 迭代次數

訓練時間複雜度：O(nfk*i)

運行時空間複雜度：O(nf+kf)

作者：Rafay Qayyum

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/RPcbUb9E06e2ddMxw0EXDA