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