TreeRangeMap Сроки и космические сложности

Я ищу guava TreeRangeMap, который, кажется, очень хорошо подходит для моих потребностей в проекте. В java-документах говорится, что он основан на стандарте (java standard?) TreeMap, который имеет O (log (n)) время для получения, размещения и следующего.TreeRangeMap Сроки и космические сложности

Но TreeRangeMap должен быть каким-то реализация дерева диапазона, что в соответствии с этим SO question имеет O (K + журнала (п)) временную сложность для запросов, O (п) пространство, с к быть размером диапазона ?. Может ли кто-нибудь подтвердить это?

Меня также очень интересует временная сложность операции TreeRangeMap.subRangeMap(). Имеет ли он тот же O (k + log (n))?

Спасибо.

источник

2013-11-29 dcernahoschi

Он, кажется, не указывает, какой алгоритм он использует, но я могу себе представить, что это фактически [B + tree] (http://en.wikipedia.org/wiki/B+_tree), который является стандартным хранилищем баз данных datastructure для поддержки запросов диапазона. – Domi

Операция 'subRangeMap' отправляет запрос и создает новую карту, поэтому, если ваш диапазон содержит значения k, вы, вероятно, закончите сложность одного запроса диапазона + k вставки. – Domi

Это вид, а не фактическая мутация или что-то еще. subRangeMap возвращает в O (1) время, а RangeMap возвращает O(log n) стоимость добавки для каждой из своих операций запроса - то есть все его операции по-прежнему принимают O(log n), только с более высоким постоянным коэффициентом.

Источник: Я «тот, кто его реализовал».

источник

2013-11-29 17:07:50

Спасибо Луи :) Я понял, на самом деле меня интересуют все значения из этого поддиапазона, что является сложностью метода asMapOfRanges(), который возвращает «Карта , V>». Или есть другой способ получить все значения из «RangeMap»? – dcernahoschi

'asMapOfRanges()' - это представление, возвращаемое в O (1) раз, и итерация по его значениям - O (n). Итерация над 'asMapOfRanges' для' subRangeMap', вероятно, будет, по сути, 'O (log n + k)'. –

Обычно мы используем дерево Range, чтобы найти точки, которые лежат в заданном интервале [x1, x2] and x1 < x2. Однако, если дерево диапазона является сбалансированным двоичным деревом (как в случае TreeMap, которое реализовано с красно-черным деревом), пути поиска до x1 (или преемника) и x2 (или предшественника) имеют стоимость O(log n). Когда мы их найдем, если там k количество точек лежит в этом диапазоне, нам нужно будет сообщить об этом, используя обход дерева, который будет иметь линейную стоимость O(k). Итак, всего O(k + log(n)).

Меня также очень интересует временная сложность TreeRangeMap.subRangeMap(). Имеет ли он тот же O (k + log (n))?

<K,V> subRangeMap(Range<K> subRange) Возвращает вид той части этого диапазона карты, которая пересекается с диапазоном, в результате чего только другой balanced-binary search Tree. Так почему бы не?

источник

2013-11-29 08:42:07 Sage

Да, похоже, это ответ, но давайте подождем тех парней, которые внедрили его, чтобы иметь слово. – dcernahoschi

TreeRangeMap Сроки и космические сложности

ответ

Смежные вопросы