Почему после того, как дерево квадрантов полностью создано, операция сравнения (для обнаружения столкновений n объектов) занимает линеарифмическое n log(n) время? Узлы рекурсивно разбиваются по регионам/квадрантам, и поиск будет сканировать дерево, отсекая пути, которые не находятся в координатах поиска, в конечном итоге находя или не находя целевые узлы в пределах границ узла, столкнувшегося с конфликтом. Каждая операция сравнивает разделенный раздел n, что похоже на log(n) время, а не n log(n).
Почему поиск по квадрантному дереву точек и областей (для обнаружения столкновений) является линеарифмическим временем?
Ответы (1)
Чтобы найти все столкновения n объектов (а в худшем случае выявить какое-то одно столкновение), необходимо выполнить около n действий - проверить окрестности каждого объекта.
Каждая такая проверка, как вы написали, занимает O(logn) времени, так что общее время достигает O(nlogn)
person
MBo
schedule
14.04.2021
nобъектов - person Growler schedule 14.04.2021