[TIL]

🍴오늘 할 일

• 모의면접 준비

우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?

선순위 큐(Priority Queue)의 시간 복잡도는 구현 방법에 따라 다르지만, 일반적으로는 다음과 같습니다.

삽입(insertion) : O(log n)
삭제(deletion) : O(log n)
최소값 검색(find-minimum) : O(1)
여기서 n은 우선순위 큐에 저장된 원소의 개수를 의미합니다.

우선순위 큐는 힙(Heap) 자료구조를 이용해 구현하는 것이 일반적입니다. 힙은 완전 이진트리(Complete Binary Tree) 형태를 띄는 트리로, 부모 노드의 값이 자식 노드의 값보다 작은(min-heap) 또는 큰(max-heap) 형태를 갖습니다.

삽입(insertion) : 새로운 원소를 힙의 마지막 위치에 추가한 후, 부모 노드와 비교하여 위치를 바꿔가며 힙의 조건을 만족하도록 조정합니다. 최악의 경우 힙의 높이(log n)만큼 비교와 교환을 해야하므로 O(log n)의 시간이 소요됩니다.
삭제(deletion) : 루트 노드(최소값 또는 최대값)를 삭제한 후, 마지막 노드를 루트 위치로 이동시키고 자식 노드와 비교하여 위치를 바꿔가며 힙의 조건을 만족하도록 조정합니다. 최악의 경우 힙의 높이(log n)만큼 비교와 교환을 해야하므로 O(log n)의 시간이 소요됩니다.
최소값 검색(find-minimum) : 루트 노드에 최소값 또는 최대값이 저장되어 있으므로 O(1)의 시간이 소요됩니다.
따라서 힙을 이용한 우선순위 큐의 시간 복잡도는 O(log n)입니다.