У меня есть дерево квадов, заполненное N случайными двумерными точками (x, y).
I что бы оценить, какова будет средняя сложность поиска в этих двух случаях
1)поиск (в пределах расстояния R от позиции x, y)
2) одной ближайшей точки (x, y)
До сих пор я рассуждал так: если мы проводим аналогию с двоичнымСредняя сложность дерева - https://en.wikipedia.org/wiki/Binary_search_tree
Что составляет
Для одного поиска средняя сложность для QuadTree должна быть примерно такой (потому что есть 4 дочерних элемента):
Где k должно зависеть от среднего числа точек, которые должны быть проверены, если они находятся внутри диапазона (но я не уверен, как его оценить, даже дляединственная точка поиск диапазона внутри круга все еще должен быть сделан).В худшем случае большого R мы должны проверить все точки, и сложность ухудшается до O (N).
Спасибо.