BST 생성 시간 복잡도

n 노드의 바이너리 힙 생성의 경우처럼 시간 복잡도는 임의의 높이 h에 atmax가 있다는 사실을 고려하여 O (n)이 아니라 O (n)이됩니다.BST 생성 시간 복잡도

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

노드를 사용하면 heapify 할 때까지 거의 O (h) 시간이 걸립니다.

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

는 비슷한 라인에, 나는 BST의 생성을 증명하고 싶었다. 이를 위해 나는 임의의 깊이 d에서 삽입을위한 atmax O (d) 시간이 걸릴 atmost 2^d 노드가있을 수 있다는 사실을 사용합니다. 따라서 수학 식 BST이 작성 또는 O (N^2) -worst 경우 복잡도 (N) -expected 시간 복잡도를 초래하는 방법 nlog 올

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

될 것이다. 위의 방정식을 더 진행하는 방법을 제안하십시오.

출처

2016-05-31 Deepankar Singh

수학 올바르지 않습니다 (트리 균형을 고려하여) N 로그와 같은 상한 준다. 대부분의 노드가 더 깊은 곳에 삽입되기 때문에 합계가 잘못 나오는 것입니다. 바이너리 힙의 생성은 O (N)입니다. 왜냐하면 모든 요소를 삽입하고 다시 heapifying하는 대신 상향식 구조가 사용되기 때문입니다. 각각을 독립적으로 삽입해야한다면 O (N log N)이됩니다. –

여기에 무엇이 잘못 되었습니까? n-node bst atleast floor (log (n)) - 높이가 필요합니다. 각 깊이 d에서 노드 높이가 15 인 균형 잡힌 bst를 고려하여 2^d 노드가됩니다. 바닥 (log (15)) 즉 3이고 레벨 3에서는 2^3 노드 즉 8 노드가됩니다. 삽입 시나리오의 경우 모든 8 개의 노드가 마지막 레벨로 이동해야하므로 2^d * h 종류의 방정식을 생성합니다. 내가 여기에없는 게 잘못이라면? –

h, d 및 n은 관련됩니다. HALF 노드는 깊이 로그 (n)에 삽입됩니다. 삽입에 깊이에 비례하는 시간이 걸리면 총 삽입 시간은 O (n) 엔). 마찬가지로, 모든 노드가 깊이 <= log (n)에 삽입되므로 총 시간은 <= O (n log n)입니다. –

마지막으로 나는 그 시리즈를 풀었다.

T = log (N) 즉, 2^T = N (노드 없음) ............... (1)
문제는 Summation_of (2^d * d)가됩니다. T. O에서 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)가

출처

2016-06-02 18:51:55

BST 생성 시간 복잡도

답변

관련 문제