힙 정렬의 시간 복잡도는?

힙 정렬은 특정 데이터 집합에 대한 정렬 알고리즘으로, 완전 이진 트리를 기반으로 합니다. 이 알고리즘은 데이터가 주어졌을 때, 이를 힙 구조로 변환한 후, 정렬된 결과를 생성합니다. 힙 정렬의 복잡성은 주로 힙을 구성하는 과정과 정렬하는 과정에서 결정됩니다. 아래 코드는 힙 정렬의 기본 구현을 보여줍니다.

위 코드를 참고하여, 힙 정렬의 전체 시간 복잡도는 어떻게 되는지 선택지에서 고르세요.

PYTHON

def heapify(arr, n, i):
    largest = i  # 가장 큰 노드
    left = 2 * i + 1  # 왼쪽 자식
    right = 2 * i + 2  # 오른쪽 자식

    if left < n and arr[largest] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 스왑
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 힙 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 정렬
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 스왑
        heapify(arr, i, 0)

답변

O(n log n) O(n^2) O(log n) O(n)

로그인 후 제출하기