Как вычислить среднюю временную сложность поиска ближайшего соседа с помощью kd-дерева?

Расчет в этой статье настолько прост, насколько это возможно для строгого анализа.

(NB это цена того, чтобы быть настоящим компьютерным ученым и инженером-программистом. Вы должны приложить усилия для изучения математики. Знание математики-это то, что отличает людей, которыедумают, что они могут писать надежные программы, от тех, кто действительно может. Джон Бентли, парень, который изобрел kd-деревья, сделал это, когда он был в средней школе. Примите это как вдохновение.)

Если вы хотите грубый интуитивная идея, которая Не строгая, вот одна.

Предположим, что мы работаем в 2d. размеры геометрических областей, представленных 2d-деревом, являются ключевыми.

В среднем одна точка разбивает домен на 2 прямоугольника примерно одинакового размера. 3 очка в 4. 7 пунктов на 8 частей. И т.д. В общем случае N точек ведут к N-1 прямоугольникам примерно одинакового размера.

Нетрудно заметить, что если домен равен 1x1, то длина стороны этих частей равна среднее значение O (sqrt (1/N)).

Когда вы ищете ближайшего соседа, вы спускаетесь по дереву к прямоугольнику, содержащему точку поиска. После этого вы использовали усилие O(log N), чтобы найти точку в пределах R = O(sqrt(1/N)) от правильной. Это просто точка, содержащаяся в листе, который вы обнаружили.

Но этот прямоугольник не единственный, который нужно искать. Вы должны по-прежнему смотреть на все остальные, содержащие точку не более чем на расстоянии R от точки поиска, уточнение R каждый раз, когда вы находите более близкую точку.

К счастью, ограничение O(sqrt(1/N)) на R обеспечивает жесткую границу среднего числа других прямоугольников, которые это может быть. В среднем это около 8, потому что каждый прямоугольник одинакового размера имеет не более 8 соседей.

Таким образом, общее усилие поиска равно O(8 log n) = O(log n).

Опять же, я повторяю, что это Не строгий анализ, но он должен дать вам представление о том, почему алгоритм O (log N) в среднем дело.