K-近鄰算法的主要時間花銷在于: 對于一個待分類的實例(設其維度為m),都要計算它與訓練數據庫(設數據庫的大小為n)中每一個訓練實例之間的距離(其時間復雜度為O(nm)),同時還要對這n個算得的距離進行排序(快速排序的平均時間復雜度是O(n logn))。所以,分類階段第二步的時間復雜度為O(nm+n logn)。
Reference:
Composite Quantization for Approximate Nearest Neighbor Search, ICML 2014
一種提高K-近鄰算法效率的新算法, 陸微微,劉晶 [J] 計算機工程與應用 2008,(04)