Выдержка из книги
Гасанова Э.Э.
Теория хранения и поиска информации
Бентли в [113] предложил метод многомерного двоичного дерева ( k - D-дерева), исходя из того, что бинарное дерево для одномерной задачи дает хороший результат. Здесь и далее, k равно мощности библиотеки, а оценки приводятся без времени перечисления ответа. В работе [114] Бентли предложил метод прямого доступа, который решает задачу за время O ( log2fc), но требует затрат по памяти порядка ks для двумерной задачи. Чтобы уменьшить требуемую память, в работе [116] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени.
![Бентли в [113] предложил метод многомерного двоичного дерева ( k - D-дерева), исходя из того, что бинарное дерево для одномерной задачи дает хороший результат. Здесь и далее, k равно мощности библиотеки, а оценки приводятся без времени перечисления ответа. В работе [114] Бентли предложил метод прямого доступа, который решает задачу за время O ( log2fc), но требует затрат по памяти порядка ks для двумерной задачи. Чтобы уменьшить требуемую память, в работе [116] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени.](/pic/3204943doaLIPZ0049189931.png)