qktlf789456   3년 전

하향식 힙 구성이 O(NlgN).상향식 힙 구성은 O(N) 이라고 합니다.

그런데 제가 보기엔..

상향식 힙 구성은 리프노드가 있는 노드부터 루트노드까지 거꾸로 계산하므로

약 1/2 개의 노드를 계산조차 할 필요가 없어서 하향식보다 더 빠른건 이해가 가는데

그래도 1/2 개의 노드가 모두 다 리프노드로 가야하는 경우에는

시간복잡도 : (1/2 lg N )    = O(NlgN) 이 나와야하는거 아닐까요..?


왜 상향식 힙 구성이 O(N)인지 도저희 이해가 가질 않습니다.

bupjae   3년 전

상향식 힙 구성에서는 노드 하나를 끝까지 다 올릴 필요가 없고, 한 번에 한 단계만 올리면 됩니다.

일단 한 단계가 올라간 노드는, 잠시 후 또 올라갈 기회를 얻게 됩니다.

qktlf789456   3년 전

bupjae 님, 잘 이해가 가질 않습니다.

리프노드가 존재하는 맨마지막노드부터 루트노드까지 순회하는데, 자식을 비교하고 내려가면서 구성하는것이 아닌, 그냥 해당 노드의 자식만 비교하면서 lg(N) 이 가능하다는 말씀이신가요?


그렇다면 하향식구성같은 경우는 이미 한번의 구성 이후에 삽입과 연산에 대해서 항상 O(lgN) 이 보장되는데,


상향식구성같은 경우는 최대값또는 최소값을 찾기 위해서 항상 O(N/2) 연산을 해야 루트노드에 원하는 값이 있을테니 상향식으로 구현한 힙정렬은 O(N^2) 가 되는건가요?

bupjae   3년 전

먼저 제가 달았던 답변은 무시해 주세요. 죄송합니다.

   

1) 상향식/하향식 구분은 처음 힙을 만들 때에만 적용되는 개념입니다.

일단 힙을 만들면 더 이상 상관 없습니다.

힙정렬은 일단 힙을 만든 이후 "힙에서 최대 원소를 제거한다"를 n 번 수행해야 하는데, "최대 원소 제거" 연산이 O(log n) 이므로 전체 수행은 O(n log n) 입니다.

즉, 힙정렬은 힙을 만들 때 상향식을 쓰든 하향식을 쓰든 최종 시간 복잡도는 O(n log n) 이 됩니다.

   

2) 상향식 힙 구성의 경우 "n/2개의 노드는 연산 안함, n/4개의 노드는 최대 1회 연산, n/8개의 노드는 최대 2회 연산, ..." 이런 식이 됩니다.

이걸 수식을 세워서 풀면 O(n) 이 나옵니다.

qktlf789456   3년 전

감사합니다, 

상향식 힙 구성의 경우 "n/2개의 노드는 연산 안함, n/4개의 노드는 최대 1회 연산, n/8개의 노드는 최대 2회 연산, ..." 이런 식이 됩니다.

이걸 수식을 세워서 풀면 O(n) 이 나옵니다.

이거군요...


혹시 마지막으로 제가 이해한게 맞는지 확인이될까요... 

예를들면은 logN 이 16인 경우에는, 

(질문1) 상향식 힙구성에 대해서 한 번 순환시 N/2 개의 노드를 순회하면서 아래자식과 비교하면서 SWAP을 진행해야하는 연산이 15번(ROOT에서 LEAF 까지) 이면 됩니다. 

따라서 N/2  * 15 = 15N/2 이므로 O(N) 이라는 표현이 성립하게되는건가요?

(질문2) 여러 구글에서 소스를 보았는데, N/2 개의 노드에 대해서 더이상 SWAP이 진행되지 않을때까지 내려가서야 멈추는 코드들도 있었습니다. 정확히 어떤게 상향식일까요?

1 : 자신의 자식들만 비교하여 SWAP 을 진행한다.

2 : 자신의 자식들과 비교하여 SWAP 을 진행하고 SWAP이 진행되었으면 아래로 이동된 노드에 대해서 또 SWAP을 고려해 내려가면서 정렬한다.

bupjae   3년 전

(질문2) 는 2번이 맞습니다. 일단 swap 이 발생했으면 아래로 이동된 노드에 대해 또 다시 swap 를 고려해야 합니다.

그렇기 때문에 리프의 부모의 부모인 n/8개의 노드는 swap 이 최대 2회 발생할 수 있고

리프의 부모의 부모의 부모인 n/16개의 노드는 swap 이 최대 3회 발생할 수 있고, ... 이런 식이 됩니다.

(질문1) 은 식의 전개 과정이 잘못되었습니다.

X =            1 * n/2 + 2 * n/4 + 3 * n/8 + ... 라고 하면

2X = 1 * n + 2 * n/2 + 3 * n/4 + 4 * n/8 + ... 가 됩니다.

아래식에서 윗식을 빼면

  X = 1 * n + 1 * n/2 + 1 * n/4 + 1 * n/8 + ... = 2 * n = O(n)

댓글을 작성하려면 로그인해야 합니다.