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

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

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

 

NextPage   2018-09-11 08:12



   1个回答 
0

如果你的搜索算法用是暴力搜索的话,如果样本是D维的,复杂度是O(D*n)

SofaSofa数据科学社区 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回答

sklearn.cluster.KMeans速度太慢,有什么解决方法?   1回答

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

NP-hard是什么意思   1回答

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

SVM的支持向量最少有几个?   1回答

有序多分类问题   2回答

k-NN的k取1会怎么样   4回答

adaboost里的learning rate是什么意思?   1回答

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

SVM里的软间隔是什么意思   2回答

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



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

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

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

我们谢绝答非所问。

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

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