kNN进行预测时计算复杂度是多少?

  统计/机器学习 监督式学习 计算复杂度    浏览次数:547        分享
0

用kNN进行预测时每预测一个样本需要的计算复杂度是多少?假设一共有n个样本的情况并且没有用KD tree。

 

NextPage   2018-09-11 08:12



   1个回答 
0

如果你的搜索算法用是暴力搜索的话,如果样本是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


  相关主题

在python中获取模型运行的时间   3回答

朴素贝叶斯的训练/预测效率如何?快吗?   1回答

NP-hard是什么意思   1回答

欠采样后概率还原问题   2回答

线性可分是什么意思?   1回答

为什么LR要用Sigmoid函数?   6回答

有序多分类问题   2回答

MLR分片模型是什么模型?   0回答

为什么说knn是惰性算法   1回答

kNN的k=1为什么训练误差为0?   4回答

KNN中K值的选择   5回答

怎么理解platt scaling?   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!