CH9-2힙의 구현과 우선순위 큐의 완성(2)
그러면 힙의 구현에 앞서서 힙의 성능평가와 관련된 이야기를 해보겠다.
배열기반일때는 시간복잡도가 다음과 같다.
$n$개의 데이가터가 이미 배열에 있다면 우선순위 비교를 $n$번해야하기 때문에 시간복잡도가 $n$이 된다..
연결리스트 기반 데이터 삽입도 마찬가지다.
그런데 사실 $O(n)$만 되어도 못쓸 알고리즘은 아니지만, $O(log_2n)$보다는 효율이 떨어진다.
트리(특히 힙)은 왜 삽입의 시간복잡도가 $O(log_2n)$의 성능을 보이는가? 쉽게 한번 설명해보겠다.
2진 트리를 그려보겠다.
이 트리는 레벨이 4이고, 총 노드는 15개 저장할 수 있음($2^4-1)$개
즉 위의 힙에서 삽입의 경우 최악의 경우 4번의 비교연산이 된다.($log_216 = 4$)
새로운 노드를 위의 힙에 추가한다고 해보자. 레벨당 한번씩 연산이 될 것임.
우리가 데이터를 삽입할때 완전이진트리에서의 기준은 ‘위에서 아래’이다. 다시 위로 올라갈 일이 없다. 그래서 레벨당 한번씩 연산이 일어나고 나면 자리를 잡는다는 것임.