Классификатор k ближайших соседей: обучающая выборка — n точек по d признаков. Определите время одного вызова classify.
Сколько стоит один прогноз
Код
import math
from collections import Counter
def classify(train: list[tuple[list[float], str]], query: list[float], k: int) -> str:
distances = []
for features, label in train:
d = math.sqrt(sum((x - y) ** 2 for x, y in zip(features, query)))
distances.append((d, label))
distances.sort()
votes = Counter(label for _, label in distances[:k])
return votes.most_common(1)[0][0]Какое время выполнения?
Ответ: O(n · d + n log n)
Расстояние до одной точки считается за O(d), до всех n точек — за O(n · d). Затем список из n расстояний сортируется за O(n log n). Голосование по k соседям — O(k), а k ≤ n, поэтому это слагаемое поглощается. Итого O(n · d + n log n). Каждый прогноз проходит по всей выборке, поэтому на больших данных k-NN медленный. Если вместо сортировки выбирать k минимальных (heapq.nsmallest), получится O(n · d + n log k).
- Подсказка 1
Сколько стоит посчитать одно расстояние, если у точки d признаков? А сколько таких расстояний?
- Подсказка 2
Не забудьте про сортировку списка из n расстояний.