algorithm - 为什么 KNN 比决策树快得多？

Question

有一次在面试中，遇到了雇主的一个问题。他问我为什么 KNN 分类器比决策树快得多，例如在字母识别或人脸识别中？

当时我完全不知道。所以我想知道我应该在哪些方面比较两种分类方法的速度性能？谢谢。

Answer 1

考虑以下数据集： N 个样本，每个样本有 k 个属性。一般来说：
1. naive KNN: O(1) [training Time] + O(NK) [query Time] = O (NK)
2. naive decision tree: O(N^2 * K * log(N)) [ training Time] + O(log(N)) [query Time] = O(N^2 * K) -- 同样对于查询时间，我们假设树是平衡的。
为了计算复杂性，我考虑了每个分类器的非常简单的实现。在实现 KNN 和决策树方面已经有了一些改进。