曾经在一次面试中，我遇到雇主的一个问题。他问我为什么在字母识别或人脸识别等任务中，KNN分类器的速度比决策树快得多？

当时我完全不知道答案。所以我想知道在速度性能方面，我应该如何比较这两种分类方法？谢谢。

回答：

考虑以下数据集：有N个样本，每个样本有k个属性。一般来说：
1. 简单KNN：O(1) [训练时间] + O(NK) [查询时间] = O(NK)
2. 简单决策树：O(N^2 * K * log(N)) [训练时间] + O(log(N)) [查询时间] = O(N^2 * K) —— 此外，对于查询时间，我们假设树是平衡的。
为了计算复杂度，我考虑了每种分类器的非常简单的实现。已经有一些改进用于实现KNN和决策树。