알고리즘 학습

8장. 마무리하기

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 책의 목표는 컴퓨터 과학에서 사용되는 기본 알고리즘과 필수 데이터 유형을 소개하는 것이었습니다. 코드의 성능을 극대화하려면 다음 데이터 유형을 효율적으로 구현하는 방법을 알아야 합니다:

가방

링크된 목록은 값을 추가할 때 O(1) 성능을 보장합니다. 배열을 사용하기로 선택한 경우 기하학적 크기 조정을 사용하여 배열의 크기를 확장해야 평균 사용량에 비해 상각된 O(1) 성능을 보장할 수 있습니다(드물게 발생하는 크기 조정 이벤트에서는 여전히 O(N) 런타임 성능이 발생하지만). 백은 일반적으로 값을 제거할 수 없으며 중복된 값이 추가되는 것을 방지하지도 못한다는 점에 유의하세요.

스택

링크된 목록은 값을 스택에 저장할 수 있으므로 push() 및 pop()은 O(1) 런타임 성능을 갖습니다. 스택은 값을 푸시하고 팝하는 스택의 top 을 기록합니다.

대기열

링크된 목록은 큐를 효율적으로 저장할 수 있으므로 enqueue() 및dequeue() 의 런타임 성능은 O(1)입니다. 큐는 연결된 목록에 first 및 last 노드를 기록하여 큐에서 값을 효율적으로 추가하고 제거합니다.

기호 표

심볼 테이블의 개방형 주소 지정 방식은 (키, 값) 쌍을 분배하는 적절한 해시 함수를 통해 놀라울 정도로 효율적입니다. 하지만 스토리지의 크기를 두 배로 늘리려면 기하학적 크기 조정이 필요하므로 이러한 크기 조정 이벤트의 빈도를 효과적으로 줄일 수 있습니다.

우선순위 대기열

힙 데이터 구조는 (값, 우선순위) 쌍을 저장하여 O(log N) 런타임 성능으로enqueue() 및 dequeue() 을 지원할 수 있습니다. 대부분의 경우 저장할 최대 값 수인 N을 미리 알 수 있지만, 그렇지 않은 경우 기하학적 크기 조정 전략을 사용하여 크기 조정 이벤트 수를 최소화할 수 있습니다.

인덱싱된 최소 우선순위 대기열

이 데이터 유형을 구현하면 힙 데이터 구조와 힙에 있는 각 값의 인덱스 위치를 저장하는 별도의 심볼 테이블이 결합됩니다. 그래프 알고리즘의 경우, 인덱싱된 최소 우선순위 큐에 저장할 값의 최대 개수인 0에서 N - 1 범위의 정수 노드 레이블만 저장하는 것이 일반적입니다(여기서 N은 인덱싱된 최소 우선순위 큐에 저장할 값의 최대 개수). 이 경우 별도의 심볼 테이블을 배열로 구현하여 매우 효율적으로 조회할 수 있습니다. enqueue() , dequeue(),decrease_priority() 를 O(log N) 런타임 성능으로 지원합니다.

그래프

인접 행렬 구조는 그래프에 가능한 모든 에지가 존재할 때 적합하며, 이는 최단 거리를 계산하는 알고리즘의 일반적인 사용 사례입니다. 노드가 0에서 N - 1 범위의 정수로 표현되는 경우 2차원 배열을 사용하여 인접 행렬을 저장할 수 있습니다. 그러나 대부분의 경우 인접성 목록 구조가 그래프를 저장하는 데 더 적합하며, 심볼 테이블을 ...