なぜKNNは意思決定ツリーよりもずっと高速ですか？

Question

インタビューを受けて、私は雇用主から質問を受けました。彼はKNN分類器が文字認識や顔認識などの意思決定ツリーよりずっと高速である理由を私に尋ねましたか？

私はその時点で全く考えていませんでした。だから私はどの条件でスピード性能の2つの分類方法を比較すべきかを知りたいですか？ありがとう。

Answer 1

次のデータセットを考えてみましょう。N個のサンプル。各サンプルにはk個の属性があります。一般的に：
1.ナイーブKNN：O（1）[トレーニング時間] + O（NK）[クエリ時間] = O（NK）
2.単純な決定木：O（N^2 * K *クエリ時間については、ツリーが均衡していると仮定します。
複雑さを計算するために、私は各分類子を非常に簡単に実装することを検討しました。すでにKNNとデシジョンツリーを実装するための改良点はほとんどありません。