Почему решение запроса минимального диапазона с временной сложностью дерева сегментов является O (Log n)? - PullRequest
Новая
       63

Почему решение запроса минимального диапазона с временной сложностью дерева сегментов является O (Log n)?

0 голосов
/ 06 мая 2018

Я пытался решить, как найти в данном массиве и двух индексах минимальное значение между этими двумя индексами в O (Log (n)). Я видел решение использования дерева сегментов, но не мог понять, почему сложность времени для этого решения равна O (Logn), потому что это не так, потому что, если ваш диапазон не совсем в пределах диапазона узла, вам нужно начать расщепление поиск.

1 Ответ

0 голосов
/ 11 января 2019

Первое доказательство:

Утверждение состоит в том, что на каждом уровне существует не более 2 узлов. Мы докажем это противоречием.

Рассмотрим дерево сегментов, приведенное ниже.

enter image description here

Скажем, в этом дереве есть 3 узла. Это означает, что диапазон находится от левого наиболее окрашенного узла до правого наиболее окрашенного узла. Но обратите внимание, что если диапазон расширяется до самого правого узла, то охватывается весь диапазон среднего узла. Таким образом, этот узел немедленно вернет значение и не будет расширен. Таким образом, мы доказываем, что на каждом уровне мы расширяем не более 2 узлов, и, поскольку существуют уровни logn, развертываемые узлы имеют значение 2⋅logn = Θ (logn).

Источник

Второе доказательство:

Существует четыре случая запроса интервала (x, y) 

FIND(R,x,y) //R is the node
% Case 1
    if R.first = x and R.last = y   
        return {R}
% Case 2
    if y <= R.middle
        return FIND(R.leftChild, x, y) 
% Case 3
    if x >= R.middle + 1 
        return FIND(R.rightChild, x, y) 
% Case 4
    P = FIND(R.leftChild, x, R.middle)
    Q = FIND(R.rightChild, R.middle + 1, y)    
    return P union Q.

Интуитивно понятно, что первые три случая уменьшают уровень высоты дерева на 1, так как дерево имеет высоту log n, а если происходят только первые три случая, время выполнения равно O (log n).

В последнем случае FIND () делит задачу на две подзадачи. Однако мы утверждаем, что это может произойти не более одного раза. После того, как мы вызвали FIND (R.leftChild, x, R.middle), мы запрашиваем R.leftChild для интервала [x, R.middle]. R.middle - это то же самое, что и R.leftChild.last. Если x> R.leftChild.middle, то это Case 1; если x <= R.leftChild, то мы назовем </p> 

FIND ( R.leftChild.leftChild, x, R.leftChild.middle );
FIND ( R.leftChild.rightChild, R.leftChild.middle + 1, , R.leftChild.last );

Однако вторая функция FIND () возвращает R.leftChild.rightChild.sum и поэтому занимает постоянное время, и проблема не будет разделена на две подзадачи (строго говоря, проблема отделена, хотя одна подзадача занимает O (1). ) время решить).

Так как тот же анализ выполняется для rightChild of R, мы заключаем, что после того, как case4 произойдет в первый раз, время выполнения T (h) (h - оставшийся уровень дерева) будет 

T(h) <= T(h-1) + c (c is a constant)
T(1) = c

, что дает: 

T(h) <= c * h = O(h) = O(log n) (since h is the height of the tree)

Следовательно, мы заканчиваем доказательство.

Источник

...