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