用kNN进行预测时每预测一个样本需要的计算复杂度是多少？假设一共有n个样本的情况并且没有用KD tree。
1个回答
如果你的搜索算法用是暴力搜索的话，如果样本是D维的，复杂度是O(D*n)
SofaSofa数据科学社区DS面试题库 DS面经
nlceyes
2018-12-25 11:01
复杂度应该含有$k$吧
-
tbh
2018-12-25 11:12
复杂度应该和k关系不大吧，我理解的是，无论k取多少，预测新样本的时候都要遍历所有的训练样本求得他们之间的距离度量值，然后再取前k个最接近的，而且一般的k的值相比于样本规模要小的多，即使考虑读取前k个样本值的操作量，应该也是可以忽略的一个小值。
-
nlceyes
2018-12-25 21:23
相关讨论
随便看看