Кто-нибудь знает, где я могу найти документацию или знать, сколько операций вставки и запросы берутся в квадранте?Производительность Quadtree
wiki говорит O (logn), но я нашел еще один источник, говорящий O (nlogn), и мне нужно знать, что истинно.
Я работаю с точки квадрантов
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C http://en.wikipedia.org/wiki/Quadtree
Поиск: O (LOGN): он должен пройти вниз по всему дереву, чтобы найти элемент. Для конкретного журнала в этом случае log_4, так как есть 4 ребенка.
Вставка (единственная точка): O (logn): вы должны пересечь дерево, чтобы найти место вставки, а затем небольшое небольшое количество работы для разделения точек в этом квадранте.
Вставить (n точек): O (nlogn), каждая точка должна быть вставлена, что приведет к nlogn. Я надеюсь, что это то, что другой сайт, который вы читаете, означает nlogn, иначе они были бы очень неправы.
Оригинальная бумага называется «Квадратные деревья, структура данных для извлечения на составных клавишах» Финкеля и Бентли.
Итак, для поиска диапазона это будет O (vlogn), где v - количество найденных vetices? – user2377181