時間複雜度可以看作是機器學習算法針對輸入大小執行速度的快慢的度量。時間複雜度總是相對於某些輸入大小（例如n）給出的。

機器學習算法/機器學習模型的複雜性通常使用大O表示法表示，大O表示法定義了算法的上限，它僅從上方限制函數。

大O表示法：算法的時間複雜度通常用大O符號表述，定義為T[n] = O(f(n))。稱函數T(n)以f(n)為界或者稱T(n)受限於f(n)。 如果一個問題的規模是n，解這一問題的某一算法所需要的時間為T(n)。T(n)稱為這一算法的“時間複雜度”。當輸入量n逐漸加大時，時間複雜度的極限情形稱為算法的“漸近時間複雜度”。

下圖顯示了算法複雜性的不同情況：

為了寫出計算複雜度，我們假設：
n =訓練示例數，d =數據維數，k =鄰居數

k最近鄰算法的複雜度

訓練時間複雜度 = O（knd）

遍歷每個訓練觀測值，並計算機器學習訓練集觀測值和新觀測值之間的距離 d。

時間相對於實例數（n）和維數（d）是線性的。

空間複雜度 = O（nd）
K最近鄰居存儲數據。測試需要較長的時間，因為您必須將每個測試實例與整個訓練數據進行比較。

邏輯迴歸的複雜度

訓練時間複雜度在邏輯迴歸中意味著解決最優化問題。
訓練時間複雜度= O（nd）

空間複雜度 = O（d）
注意： 邏輯迴歸對於低延遲應用程序非常有用。

支持向量機（SVM）的複雜度

訓練時間複雜度 = O（n²）
注意：如果n大，請儘量避免使用支持向量機（SVM）。

運行時複雜度 = O（k * d）
K =支持向量數，d =數據的維數

決策樹的複雜度

訓練時間複雜度= O(n*log(n)*d)

n=訓練集中的樣本數

d=數據的維數

運行時複雜度= O(樹的最大深度)

注意:當我們有大量低維數據時，我們使用決策樹。

隨機森林的複雜度

訓練時間複雜度= O(n*log(n)*d*k)

k=決策樹的數量

注:當我們有大量具有合理特徵的數據時。然後我們可以使用多核並行化我們的機器學習模型來訓練不同的決策樹。

運行時複雜度= O(樹的深度* k)

空間複雜度= O(樹的深度*k)

注意:隨機森林相對於其他機器學習算法速度更快。

樸素貝葉斯的複雜度

訓練時間複雜度 = O（n * d）
運行時複雜度 = O（c * d）
我們必須為每個類'c'檢索特徵

結論：

如果您有大量數據，則根據要解決的業務問題選擇算法。如果需要降低計算複雜性，可以嘗試減少數據的維數。

閱讀更多 不靠譜的貓 的文章

關鍵字: 機器學習 機器 算法