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)