k-NN 計算複雜度

使用樸素搜索方法（無 kd 樹或類似方法）的k -NN 算法的時間複雜度是多少？

考慮到超參數k，我對它的時間複雜度很感興趣。我發現了矛盾的答案：

1. O(nd + kn)，其中n是訓練集的基數，d是每個樣本的維度。[1]
2. O(ndk)，其中n是訓練集的基數，d是每個樣本的維度。[2]

[1] http://www.csd.uwo.ca/courses/CS9840a/Lecture2_knn.pdf（第 18/20 頁）

[2] http://www.cs.haifa.ac.il/~rita/ml_course/lectures/KNN.pdf（第 18/31 頁）

假設是固定的（就像兩個鏈接的講座一樣），那麼您的算法選擇將決定您的計算是否需要運行時或運行。

首先，讓我們考慮一個運行時算法：

• 初始化對於所有觀察在訓練集中
• 對於每個訓練集觀察, 計算，新觀測到訓練集觀測的距離
• 為了到: 遍歷所有訓練集觀察，選擇索引用最小的價值和. 通過設置選擇這個觀察.
• 返回選定的索引

每個距離計算需要運行時，所以第二步需要運行。對於第三步中的每次迭代，我們執行通過循環訓練集觀察來工作，因此整個步驟需要工作。第一步和第四步只需要工作，所以我們得到一個運行。

現在，讓我們考慮一個運行時算法：

• 初始化對於所有觀察在訓練集中
• 為了到: 遍歷所有訓練集的觀察結果併計算距離在選定的訓練集觀察和新觀察之間。選擇索引用最小的價值. 通過設置選擇這個觀察.
• 返回選定的索引

對於第二步中的每次迭代，我們計算新觀測值與每個訓練集觀測值之間的距離，要求為迭代工作，因此整體工作。

兩種算法的區別在於，第一種算法預先計算並存儲距離（需要額外的內存），而第二個沒有。然而，鑑於我們已經存儲了整個訓練集，需要記憶，以及向量，需要存儲，兩種算法的存儲是漸近相同的。因此，更好的漸近運行時間使第一個算法更具吸引力。

值得注意的是，可以獲得運行時使用算法改進：

• 對於每個訓練集觀察, 計算，新觀測到訓練集觀測的距離
• 運行快速選擇算法來計算最小距離運行
• 返回不大於計算值的所有索引最小距離

這種方法利用了一個事實，即存在有效的方法來找到未排序數組中的最小值。

引用自：https://stats.stackexchange.com/questions/219655