tjdgns9246   4달 전

안녕하세요, 요즘 자료구조 책을 보면서 다시 공부를 하고있는 유저입니다.

제가 지금 Priority Queue를 공부하고 있는데요,

여기서 Heap을 이용한 일반적인 Push()를 하게되면 시간 복잡도가 O(log(n))이라고 알고있습니다.

그런데 책에서 이 Push()함수에다가 이진탐색을 결합시키면 시간복잡도를 O(log(log(n)))으로 줄일 수 있다고 합니다.

그래서 3일동안 고민해서 소스를 만들고 테스트를 해봤는데... 결과가 아래와 같이 나옵니다.

input  :   7 16 49 82  5 31  6  2 44
output :  49 82 31 44  5 16  6  2  7

정상적인 결과로는 49 와 82가 바뀐 82 49 31 44  5 16  6  2  7 가 되야하는데요..

왜 이렇게 되는지 이해가 되지 않네요... @.@

또한 궁금한 점은 제 소스의 시간복잡도가 O(log(log(n)))이 맞는지 궁금합니다.

알려주실 고수분들 계신가요?

yukariko   4달 전

슬랙에서 얘기 나눈것을 정리해보자면

우선 시간복잡도는 밀어내는 과정이 있기때문에 O(lgN)이 될수밖에 없습니다.

여기서 O(lglgN)은 어느 노드에 위치해야 하는지를 찾는것을 의미한다고 생각됩니다.


구현할 목표는 정해졌고.. 이것을 이진탐색을 이용하려면 우선 데이터가 정렬된 상태여야 합니다.

그런데 힙은 자신의 직접 연결되는 부모간에만 대소관계가 있고 나머지와는 그렇지 못하기 때문에 위 코드 같은 이진탐색은 불가능하다고 생각됩니다.

또한, 저 코드는 결국 1~ N/2 사이의 이진탐색이기 때문에 O(lgN)의 시간복잡도를 갖습니다.


대신 루트노드부터 자기노드까지의 경로로만 생각한다면 정렬된 구조를 갖기때문에 이진탐색이 가능합니다.

자기노드의 깊이를 h라고 하면 h는 lgN일 것이고 1~h 와의 이진탐색이기 때문에 O(lglgN)이 되는 구조로 생각됩니다.

이제 up = 1, down = h로 놓고 이진탐색을 수행하는데, 실제 노드 인덱스는 N >> (h - mid) 같은 방식으로 진행하면 될것 같습니다.

tjdgns9246   3달 전

yukariko 님,

감사합니다. O(log(log(n)))이 그런 뜻을 가지고 있었군요.. ㅎㅎㅎㅎ

덕분에 또 하나 배워갑니다 ^^

참고로, 제 소스에서 잘못된 부분은  42번째 줄에서 "down = i / 2" 에서 "down = i - 1"로 고치니 정상적으로 이진탐색이 되는 것 같네요.

아래의 소스로 정상적으로 push가 이루어지네요.

input : 7 16 49 82 5 31 6 2 44
output : 82 49 31 44 5 16 6 2 7

좋은 하루 되세요 ^^

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