Временная сложность создания BST

Как и в случае бинарного создания кучи русского узла, его временная сложность оказывается O (п) не NLog (п) с учетом того, что на любой высоте ч там будет atmaxВременная сложность создания BST

$\frac{n}{2^{h+1}}$

Узлы с требуемым наименьшим временем O (h) для heapify.

$\sum_{h=0}^{log(n)}\frac{n}{2^{h+1}}*O(h)=O(n)$

На подобных линий, я хотел доказать создание BST. Для этого я использую тот факт, что на любой глубине d могут быть самые узкие 2^d узлы, которые будут принимать atmax O (d) время для вставки. Таким образом, уравнение будет

$\sum_{d=0}^{log(n)}{2^d}*O(d)$

Каким образом это уравнение приводит к NLog (п) -expected временной сложности создания BST или O (N^2) -worst сложности дела. Пожалуйста, предложите способ дальнейшего перехода от уравнения выше.

источник

2016-05-31 Deepankar Singh

Ваш математике является неправильным. Ваши суммы ошибочны, потому что большинство узлов вставлены на большие глубины. Создание двоичной кучи - это O (N), потому что вместо вставки используется последующая конструкция, а затем heapifying каждый элемент. Если вам нужно было вставить каждый из них самостоятельно, это будет O (N log N). –

Что здесь не так, пожалуйста, укажите, что для n-узла bst atleast floor (log (n)) требуется высота, на каждой глубине d она будет иметь 2^d-узел, учитывая сбалансированную bst из 15 высоты узла, выйдя на быть пол (log (15)) т.е. 3, а на уровне 3 он будет иметь 2^3 узла, т.е. 8 узлов. и для сценария вставки все 8 узлов должны будут опуститься до своего последнего уровня, создав таким образом уравнение типа 2^d * h. Если это неправильно, то я здесь отсутствует? –

h, d и n связаны между собой. Это проще сделать: HALF: узлы будут вставлены в журнал глубины (n), поэтому, если вставка занимает время, пропорциональное глубине, то общее время вставки равно> = O (0,5 n log n)> = O (n log п). Точно так же ВСЕ узлы будут вставлены на глубину <= log (n), поэтому общее время <= O (n log n) –

Наконец-то я решил эту серию.

let T = log (N) ie 2^T = N (нет узлов) ............ (1)
проблема становится суммой (2^d * d) где г находится в диапазоне от о до Т. так

 

    G(T)  = 0*2^0 + 1*2^1 + 2*2^2 + ..... + T*2^T.
 
    2G(T)  =   0*2^1 + 1*2^2 + ..... +(T-1)*2^T + T*2^(T+1) 
 
    2G(T)-G(T) = 0  - 2^1 -2^2 - ..... - 2^T + 2T*2^T
 
    G(T)  =  - 2^(T+1)-2 + 2T*2^T 
    G(T)  = 2((T-1)2^T +1) 
    which is  = 2((log(N)-1)N +1)...........from (1)

Таким образом, дает верхнюю границу N журнала (N), (с учетом сбалансированных деревьев)

источник

2016-06-02 18:51:55

Временная сложность создания BST

ответ

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