로그인
로그인

마인드 맵 갤러리 데이터 구조 마인드 맵

데이터 구조 마인드 맵

데이터 구조, 선형 테이블, 스택, 큐 등의 기본 개념을 포함한 데이터 구조에 대한 마인드 맵입니다. 도움이 되었기를 바랍니다!

2023-11-07 11:40:27에 편집됨

슈퍼직장인

최근 작업 더 많은 작업 보기>>

(III) 저산소 유도 인자 프롤릴 하이드 록 실라 제 억제제
이것은 (III) 저산소증-유도 인자 프롤릴 하이드 록 실라 제 억제제에 대한 마인드 맵이며, 주요 함량은 다음을 포함한다 : 저산소증-유도 인자 프롤릴 하이드 록 실라 제 억제제 (HIF-PHI)는 신장 빈혈의 치료를위한 새로운 소형 분자 경구 약물이다. 1. HIF-PHI 복용량 선택 및 조정. Rosalasstat의 초기 용량, 2. HIF-PHI 사용 중 모니터링, 3. 부작용 및 예방 조치.
Kuka 산업용 로봇의 개발 및 Kuka 산업 로봇의 모션 제어 명령
이것은 Kuka Industrial Robots의 개발 및 Kuka Industrial Robot의 모션 제어 지침에 대한 마인드 맵입니다. 주요 내용에는 쿠카 산업 로봇의 역사, 쿠카 산업 로봇의 특성, 쿠카 산업 로봇의 응용 분야, 2. 포장 프로세스에서 쿠카 로봇은 빠르고 일관된 포장 작업을 달성하고 포장 효율성을 높이며 인건비를 줄입니다. 2. 인건비 감소 : 자동화는 운영자에 대한 의존성을 줄입니다. 3. 조립 품질 향상 : 정확한 제어는 인간 오류를 줄입니다.
1.1 컴퓨터 네트워크 요약
408 컴퓨터 네트워크가 너무 어렵습니까? 두려워하지 마세요! 나는 피를 구토하고 지식 맥락을 명확히하는 데 도움이되는 매우 실용적인 마인드 맵을 분류했습니다. 컨텐츠는 매우 완전합니다. 네트워크 아키텍처에서 응용 프로그램 계층, TCP/IP 프로토콜, 서브넷 디비전 및 기타 핵심 포인트에 이르기까지 원칙을 철저히 이해하는 데 도움이 될 수 있습니다. 📈 명확한 논리 : Mindmas 보물, 당신은 드문 기회가 있습니다. 서둘러! 이 마인드 맵을 사용하여 408 컴퓨터 네트워크의 학습 경로에서 바람과 파도를 타고 성공적으로 해변을 얻으십시오! 도움이 필요한 친구들과 공유해야합니다!

데이터 구조 마인드 맵

슈퍼직장인

최근 작업 더 많은 작업 보기>>

추천 사항
개요

데이터 구조
- 11
슈퍼직장인
데이터 구조 - 선형 테이블
- 4
슈퍼직장인
데이터 구조 선형 테이블 스택 큐 지식 포인트 노트
- 7
슈퍼직장인
데이터 구조 2장 - 선형 테이블
- 6
슈퍼직장인
데이터 구조 및 알고리즘의 기본 개념
- 4
슈퍼직장인
데이터 구조 부분
- 3
슈퍼직장인
데이터 구조 선형 테이블
- 6
슈퍼직장인
데이터 구조
- 9
슈퍼직장인
데이터 구조 코스 프레임워크
- 6
슈퍼직장인
데이터 구조
- 8
슈퍼직장인

데이터 구조

1장 소개

1. 데이터 구조의 기본 개념

1. 기본 개념 및 용어

1.데이터

정보 전달체는 객관적인 사물의 속성을 설명하는 컴퓨터가 인식하고 처리할 수 있는 숫자, 문자 및 모든 기호의 집합입니다.

2. 데이터 요소

데이터 항목으로 구성된 데이터의 기본 단위로, 나눌 수 없는 가장 작은 단위

3. 데이터 객체

동일한 속성을 가진 데이터 요소의 모음, 데이터의 하위 집합

4.데이터 유형

값의 집합과 컬렉션에 정의된 작업 집합입니다.

원자 유형

가치는 나눌 수 없다

구조 유형

가치를 더 나눌 수 있다

추상 데이터 유형

5. 추상 데이터 유형

1. 정의: 수학적 모델과 모델에 정의된 일련의 작업

2. 특성: 정의는 논리적 특성 집합에만 의존하며 컴퓨터 내부에서 어떻게 표현되고 구현되는지와는 아무런 관련이 없습니다.

3. 표현: (데이터 개체, 데이터 관계, 기본 작업 집합)

6.데이터 구조

1. 구조: 데이터 요소 간의 관계

2. 정의: 서로 하나 이상의 특정 관계를 갖는 데이터 요소의 모음입니다.

3. 내용 : 논리적 구조, 저장 구조, 데이터 연산

논리적 구조: 알고리즘 설계

저장 구조: 알고리즘 구현

2. 데이터 구조의 세 가지 요소

1. 데이터의 논리적 구조

1. 정의: 저장 장치와 관련이 없고 컴퓨터와 독립적인 데이터 요소 간의 논리적 관계입니다.

2. 분류

선형 구조

선형 테이블

1-1

비선형 구조

모으다

동일한 세트에 속함

나무

일대다

그림/네트워크

다수 대 다수

2. 데이터 저장 구조

1. 정의: 컴퓨터의 데이터 구조 표현(이미지/물리적 구조라고도 함)

2. 포함: 데이터 요소의 표현 및 관계의 표현

3. 분류

순차 저장

장점: 무작위 액세스, 요소가 최소한의 저장 공간을 차지함

단점: 인접한 저장 장치 블록만 사용할 수 있으므로 외부 조각화가 더 많이 발생합니다.

체인 스토리지

장점: 조각화 없음

단점: 저장소 포인터는 추가 저장소 공간을 차지하며 순차적으로만 액세스할 수 있습니다.

인덱스 저장

정의: 추가 인덱스 테이블을 생성합니다. 각 항목을 인덱스 항목(키워드, 주소)이라고 합니다.

장점: 빠른 검색

단점: 저장 공간을 더 많이 차지하며, 데이터를 추가하고 삭제하려면 인덱스 테이블을 수정해야 하므로 시간이 더 걸립니다.

해시 저장

정의: 요소의 키워드를 기반으로 요소의 저장 주소(해시 저장소)를 직접 계산합니다.

장점: 노드 검색, 추가 및 삭제가 빠릅니다.

단점: 해시 함수가 좋지 않으면 요소 저장 단위 충돌이 발생하여 시간과 공간의 비용이 증가하게 됩니다.

3. 데이터 작업

1. 동작의 정의 : 논리적 구조에 따른 동작의 기능을 지적한다.

2. 작업 구현: 저장소 구조에 따라 작업의 구체적인 작업 단계를 지적합니다.

질문 요약

1. 오류가 발생하기 쉬움

1. 논리적 구조에 속한다

주문 목록

2. 순환 큐는 시퀀스 테이블로 표현되는 큐이며 추상적인 데이터 구조가 아닙니다.

3. 서로 다른 노드의 저장 공간은 불연속적일 수 있지만, 노드 내 저장 공간은 연속적이어야 합니다.

4. 두 가지 다른 데이터 구조, 즉 논리적 구조와 물리적 구조는 정확히 동일할 수 있지만 데이터 작업은 다릅니다.

이진 트리와 이진 정렬 트리는 노드를 검색하는 시간이 다릅니다.

2. 알고리즘 및 알고리즘 평가

1. 알고리즘의 기본 개념

1. 정의: 특정 문제를 해결하기 위한 단계에 대한 설명, 유한한 지침 순서

2.특징

1. 유한성

2. 확실성

3. 타당성

4.입력

5. 출력

3. 좋은 알고리즘

1. 정확성

2. 가독성

3. 견고성

4. 효율성과 낮은 저장 요구 사항

2. 알고리즘 효율성 측정

1. 시간복잡도 O(n)

정의: 문제의 크기가 증가함에 따라 알고리즘의 실행 시간이 얼마나 빨리 증가하는지 측정합니다.

2. 공간 복잡도 S(n)

1. 정의: 문제의 크기가 증가함에 따라 알고리즘에 필요한 공간이 얼마나 빨리 증가하는지 측정합니다.

2. 알고리즘은 제자리에서 작동합니다. 알고리즘에 필요한 보조 공간은 일정합니다. 즉, O(1)입니다.

질문 요약

1. 오류가 발생하기 쉬움

1. 길이가 m, n인 두 개의 오름차순 연결 리스트를 m n의 내림차순 연결 리스트로 병합합니다(더 작은 요소, 헤드 보간법 사용).

1. 최선의 경우: O(min(m,n))

덜 필요한 것

2. 최악의 경우: O(max(m,n)) =O(m n)

두 개의 연결된 목록이 모두 한 번 순회되었습니다.

2. 시간복잡도 계산

1.합 = 나;

오(n^1/2)

k 번째 시간: 합 = 1 2 3 ... k ≥n

2.i=i*2

O(log²n)

3. 재귀 알고리즘

1.T(n)=2T(n/2) n (n>1) (n=1일 때: T(n)=1)

O(nlog2n)

2. n=2^k라고 가정하고 먼저 재귀 조건에 따라 T(2^k)의 일반식을 찾은 다음 이를 n으로 변환합니다. 즉, 시간 복잡도를 얻습니다.

3. 동일한 알고리즘이라도 구현된 언어의 레벨이 높을수록 실행 효율성은 낮아집니다.

2장 선형표

1. 선형 테이블의 정의 및 기본 동작

1. 선형 테이블의 정의

1.정의: 동일한 데이터 유형의 유한 시퀀스

2. 참고: 선형 목록은 논리적 구조이고, 순차 목록 및 연결 목록은 저장 구조를 나타냅니다.

2. 선형 테이블의 기본 동작

1. 참고: &는 C에서 참조를 나타냅니다. 포인터 변수가 전달되어 함수 본문에서 변경되어야 하는 경우 포인터 변수에 대한 참조를 사용해야 합니다(포인터에 대한 포인터는 C에서도 사용할 수 있음).

2. 주요업무

2. 선형 테이블의 순차적 표현

1. 시퀀스 테이블의 정의

1. 시퀀스 테이블에는 세 부분이 필요합니다.

저장 공간의 시작 위치

시퀀스 테이블의 최대 저장 공간

시퀀스 테이블의 현재 길이

2. 정적 할당

3. 동적 할당

4. 동적 할당문

C 언어: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

C: L.data=new ElemType[InitSize];

5. 참고: 동적 할당은 체인 저장소가 아니며 순차적 저장소 구조이기도 하며 물리적 구조는 변경되지 않습니다. 이는 임의 액세스 방법이지만 할당된 공간 크기는 런타임에 결정될 수 있습니다.

6. 특징: 랜덤 액세스, 높은 저장 밀도, 삽입 및 삭제에는 많은 수의 요소 이동이 필요합니다.

2. 시퀀스 테이블에 대한 기본 작업 구현

1. 삽입 연산 O(n)

2. 삭제 연산 O(n)

3. 값으로 검색(순차검색) O(n)

질문 요약

1. 오류가 발생하기 쉬움

1. 선형 테이블은 유한 시퀀스여야 합니다.

2. 순서표의 i번째 위치에 숫자를 삽입합니다. i의 유효한 값은 1≤i≤n 1입니다.

n번째 위치에 삽입하는 것은 테이블 끝에 추가하는 것과 같습니다.

2. 알고리즘

1. 시퀀스 목록의 모든 요소를 반전

1. 전반부를 스캔하고 i번째 요소(0≤i<n/2)를 후반부의 해당 요소(n-i-1)로 교환합니다.

스페이스오(1)

1.1 A[m n] 배열에는 길이가 m과 n인 두 개의 시퀀스 테이블이 있으며 위치가 서로 바뀌었습니다.

1. 생각

1. 먼저 A에 있는 모든 요소의 순서를 반대로 바꿉니다(n,n-1,...,m,m-1,...,1).

2. 그런 다음 처음 n개 요소와 마지막 m개 요소에 각각 역순 알고리즘을 사용합니다.

2. 깨닫다

1. Reverse() 함수를 설정하여 왼쪽에서 오른쪽 위치로 역순을 구현합니다.

2. 길이가 m과 n인 두 시퀀스 테이블의 위치 교환을 실현하도록 Exchange() 함수를 설정합니다.

3.Reverse()에는 세 개의 매개변수가 있습니다. 첫 번째는 위의 방법에 따라 반전해야 하는 배열입니다. 왼쪽 요소를 해당(오른쪽-왼쪽-1) 요소로 바꿉니다.

4.Exchange()에는 세 개의 매개변수가 있습니다. 첫 번째 매개변수는 배열 A이고 나머지 길이는 m과 n입니다.

5.Exchange()는 Reverse()를 호출하여 처음으로 매개변수(A,0,m n-1)를 전달합니다. 두 번째(A,0,n-1), 세 번째(A,n,mn-1)

3. 유사한 설명

1. A의 요소를 왼쪽 p 위치로 이동합니다.

1. 첫 번째 p 요소를 배열 B로 처리합니다.

2. 마지막 n-p 요소를 배열 C로 처리합니다.

3. 포지션 B와 C의 교환을 완료합니다.

시간 O(n), 공간 O(1)

2. 순차 목록(순서가 지정되지 않음)은 x 값을 가진 모든 데이터 요소를 삭제합니다.

1. 삽입되어야 할 현재 위치인 x(초기값 = 0)와 같지 않은 요소의 개수를 k를 이용하여 기록한다.

2. 시퀀스 테이블을 스캔합니다. x가 아닌 경우 이 요소를 k번째 위치에 넣으면 k가 1씩 증가합니다.

3. 마지막으로 수정된 테이블의 길이 = k

시간 O(n), 공간 O(1)

2.1 순차 목록(비순차)은 s와 t 사이의 값을 가진 모든 요소를 삭제합니다.

1. s보다 작거나 t보다 큰 요소 수를 기록하려면 k를 변경하세요.

3. 순서화된 시퀀스 목록은 주어진 값 s와 t 사이의 모든 요소를 삭제합니다.

1. 먼저 첫 번째 요소 ≥ s(첫 번째 삭제된 요소)를 찾습니다.

2. 첫 번째 요소 찾기 > t(마지막으로 삭제된 요소 다음의 요소)

3. 다음 요소를 직접 앞으로 이동하고 마지막으로 테이블 길이를 수정합니다.

4. 순서가 지정된 목록에서 중복된 값을 가진 모든 요소를 제거합니다.

1. 아이디어는 직접 삽입 정렬과 유사합니다. 처음에는 첫 번째 요소가 반복되지 않는 순서 목록으로 간주됩니다.

2. 다음 요소가 이전 비반복 순서 목록의 마지막 요소와 동일한지 차례로 확인합니다.

3. 두 개의 포인터: i는 항상 정렬된 목록의 마지막 요소를 가리키고, j는 작업 포인터입니다.

4.1 순서가 있는 목록을 순서가 없는 목록으로 변경

1. 해시 테이블을 사용하면 시간은 O(n)입니다.

5. 두 개의 순서 목록을 하나의 순서 목록으로 병합하고 함수로 결과를 반환합니다.

1. 함수에는 세 개의 매개변수가 있으며, 마지막 매개변수는 결과 연결 목록, 참조 유형입니다.

2. 두 연결된 목록의 헤더 요소를 순서대로 비교하고 더 작은 것을 새 목록에 넣습니다.

3. 어떤 테이블이 남아 있는지 확인하고 남은 부분을 새 테이블의 끝에 추가합니다.

6. 길이 L의 오름차순 S, 중앙값은 ┍L/2┑입니다. 두 개의 동일한 길이의 오름차순 시퀀스 A와 B의 중앙값 찾기

1. 먼저 A와 B의 중앙값 a와 b를 찾아 비교합니다.

2. a=b이면 a는 필수 중앙값입니다.

3. a<b인 경우 A의 작은 절반을 버리고 B의 큰 절반을 버립니다. 두 개의 버리는 길이는 동일해야 합니다.

4. a>b인 경우 A의 더 큰 절반을 버리고 B의 더 작은 절반을 버립니다. 두 개의 폐기 길이가 동일해야 합니다.

5. 두 시퀀스에 하나의 요소만 포함되고 더 작은 요소가 필요한 중앙값이 될 때까지 2, 3, 4단계를 반복합니다.

참고: 매번 폐기되는 길이가 동일한지 확인하려면

1. 수열이 홀수인 경우에는 중간점이 유지됩니다.

2. 순서가 짝수인 경우에는 중간지점의 위치가 상대적으로 첫 번째이므로, 따라서 작은 부분을 폐기할 때에는 중간점도 함께 폐기해야 한다. 폐기된 길이가 더 큰 부분과 동일한지 확인하려면

3. 3번과 4번의 경우는 별도로 논의할 필요가 있다.

시간 O(log2n), 공간 O(1)

7. x > n/2 값을 갖는 요소의 개수를 주 요소라고 합니다. A의 주 요소를 찾습니다.

1. 후보 주요요소 선정

1. c에 첫 번째 숫자 a를 후보 주요소로 대입하고, a의 발생 횟수를 1로 기록한다.

2. 다음 요소 = a이면 1을 계산하고, 그렇지 않으면 -1을 계산합니다.

3. 카운트가 0으로 감소하면 후보 메인 요소를 교체하고 다음 숫자를 c에 넣고 re-count = 1

4. 끝까지 과정을 반복하세요

2. c의 요소가 실제 주 요소인지 확인

1. c의 발생 횟수를 계산하기 위해 다시 스캔합니다. >n/2이면 주 요소입니다.

시간 O(n), 공간 O(1)

참고: 계수 정렬을 사용하는 경우: 시간 O(n), 공간 O(n)

8. 배열에 나타나지 않는 가장 작은 양의 정수를 찾는데 시간이 덜 걸립니다.

1. 공간을 시간으로 교환하고 표시용 배열 B[n]을 할당하고 1~n의 양의 정수가 나타나는지 기록하며 초기값은 모두 0이다.

2. 0보다 작거나 같은 숫자, n보다 큰 숫자에 대해서는 아무런 조치도 취하지 않습니다.

3. 0<A[i]≤n이면 B[A[i]-1]=1로 두고, 그렇지 않으면 아무 작업도 수행하지 않습니다.

4. B를 탐색하여 첫 번째 B[i]==0을 찾고 i 1을 반환합니다. 모두 0이 아니면 i 1을 반환합니다(루프에서 점프할 때 i=n).

3. 선형 테이블의 연결 표현

1. 단일 연결 리스트의 정의

1. 노드 유형 설명

2. 특징: 공간낭비, 랜덤접속 불가

3. 헤드 포인터와 헤드 노드의 차이점

1. 헤드 노드 유무에 관계없이 헤드 포인터는 항상 연결 리스트의 첫 번째 노드를 가리킵니다.

2. 헤드 노드는 헤드 노드가 있는 연결 리스트의 첫 번째 노드이며 일반적으로 정보를 저장하지 않습니다.

4. 헤드 노드 도입의 장점

1. 연결리스트의 첫 번째 위치에서의 연산은 다른 위치에서의 연산과 일치한다.

2. 연결된 리스트가 비어 있는지 여부에 관계없이 헤드 포인터는 헤드 노드의 null이 아닌 포인터를 가리키며 빈 리스트와 비어 있지 않은 리스트는 동일하게 취급됩니다.

2. 단일 연결 목록에 대한 기본 작업 구현

1. 연결리스트를 생성하기 위한 헤드 삽입 방법

2. tail 삽입 방식을 사용하여 연결리스트 생성

3. 일련번호로 노드 값 찾기

4. 값으로 테이블 노드 찾기

5. 노드 삽입 작업

확장: 정방향 삽입 연산을 역방향 삽입 연산으로 변환한 후 두 노드의 데이터를 교환합니다. 시간 복잡도는 O(1)입니다.

6. 노드 삭제 작업

먼저 선행 노드를 찾은 다음 노드를 삭제합니다. O(n)

확장: 먼저 후속 노드와 데이터를 교환한 후 후속 노드를 삭제합니다. O(1)

7. 테이블 길이 연산 찾기

데이터 노드 수 계산

3. 이중 연결 리스트

1. 이중 연결 목록의 노드 유형에 대한 설명

2. 삽입 작업

3. 삭제 작업

4. 순환 연결 리스트

1. 순환형 단일 연결 리스트

1. Null 조건: 헤드 노드의 포인터가 헤드 포인터를 가리키는지 여부

2. 단일 연결 리스트의 헤드와 테일에 대해 작업할 때: 헤드 포인터를 설정하지 않고 테일 포인터만 설정하는 것이 더 효율적입니다.

3. 모든 노드에서 시작하여 전체 연결 리스트를 탐색할 수 있습니다.

2. 순환 이중 연결 리스트

Null 조건: 헤드 노드의 이전 필드와 다음 필드는 모두 헤드 포인터를 가리킵니다.

5. 정적 연결리스트

1. 정의: 배열을 사용하여 데이터 필드와 포인터 필드도 포함하는 체인형 저장 구조를 설명합니다. 포인터는 커서라고도 하는 노드의 상대 주소(배열 첨자)입니다.

2.양식

3.종료 플래그: next==-1

4.주의

1. 시퀀스 테이블과 마찬가지로 연속적인 메모리 공간을 미리 할당해야 한다

2. 삽입 및 삭제에는 포인터 수정만 필요하며 요소 이동은 필요하지 않습니다.

3. 포인터를 지원하지 않는 고급 언어(Basic)에서 매우 영리함

6. 시퀀스 리스트와 링크드 리스트의 비교

1.액세스 방법

시퀀스 목록은 순차적으로 접근할 수도 있고 무작위로 접근할 수도 있습니다. 연결 목록은 헤드에서만 순차적으로 접근할 수 있습니다.

2. 논리적 구조와 물리적 구조

3. 찾기, 삽입, 삭제

1. 값으로 검색

고장난 경우 O(n)

주문 시 Sequence Table을 반씩 O(log2n)로 조회 가능

2. 일련번호로 검색

시퀀스 목록은 O(1), 연결 목록은 O(n)

4. 공간배분

5. 저장구조 선택방법

1. 보관 고려사항

연결리스트는 길이와 저장 크기를 추정하기 어렵지만 연결리스트의 저장 밀도가 낮은 경우에 사용됩니다.

2. 운영에 따른 고려사항

시퀀스 테이블을 사용하여 일련번호로 데이터 요소에 자주 액세스

3. 환경 고려 사항

순차 목록은 구현하기 쉽고 연결 목록은 포인터를 기반으로 합니다.

더 안정적이라면 시퀀스 목록을 선택하고, 더 동적이라면 연결 목록을 선택하세요.

질문 요약

1. 오류가 발생하기 쉬움

1. 다양한 논리적 구조를 표현하는데 있어 순차 저장 구조보다 체인 저장 구조가 더 편리합니다.

2. 순차 저장은 선형 구조뿐만 아니라 그래프와 트리(완전 이진 트리)의 구조에도 사용할 수 있습니다.

3. 정적 연결리스트는 큰 연속 공간을 할당해야 하며, 삽입 및 삭제에는 이동 요소가 필요하지 않습니다.

4. 큐를 표현하기 위해 단일 연결 리스트를 사용하는 경우 꼬리 포인터가 있는 순환 연결 리스트를 사용해야 합니다.

5. 1차원 배열이 주어졌을 때 순서가 있는 단일 연결 리스트를 만드는 데 걸리는 최소 시간은 O(nlog2n)입니다.

먼저 배열을 정렬한 다음 단일 연결 리스트를 구성합니다.

6. 연결 목록에서 일반적으로 사용되는 작업은 마지막 요소 뒤에 삽입하고 첫 번째 요소를 삭제하는 것입니다.

1. 헤드 노드와 테일 포인터가 없는 단일 원형 연결 리스트

2. 이중연결리스트라도 tail 포인터가 없는 한 tail node를 찾아야 하며, 시간은 O(n)이다.

조심하세요

1. 노드 삽입 시: 먼저 삽입된 노드의 후속 노드에 연산을 수행한 후 원래 노드에 연산을 수행합니다.

3장 스택과 큐

1.스택

1.스택의 기본 개념

1. 스택의 정의: 한쪽 끝에 삽입과 삭제가 있는 선형 목록

2.스택의 특성: 후입선출(last in, first out)

3. 스택의 기본 작업: 제한이 없으며 직접 사용할 수 있습니다.

2. 스택의 순차적 저장 구조

1. 순차 스택 구현

1. 스택 상단 포인터: S.top 스택 상단 요소: S.data[S.top]

2. 스택에 푸시: 포인터가 먼저 1만큼 증가한 다음 값이 스택의 최상위 요소로 전송됩니다.

3. 스택 팝: 먼저 스택 상단에 있는 요소의 값을 가져온 다음 스택 상단에 있는 포인터를 1만큼 감소시킵니다.

4. 공허한 판단과 완전한 판단의 조건: 실제 주어진 조건이 다르기 때문에 다양합니다.

2. 순차 스택의 기본 동작

3. 공유 스택

1. 정의: 공유 공간의 양쪽 끝에 두 스택의 바닥을 설정하고 두 스택의 상단이 중앙을 향해 확장됩니다.

2. 공백 판단: top0=-1 top1=MaxSize

3. 전체 문장: top1-top0=1

이 공식은 위의 무효 판단 조건에서만 유효합니다. 조건이 다르면 공식도 달라집니다.

4. 스택에 넣습니다. top0은 먼저 1을 더한 다음 값을 할당하고, top1은 먼저 1을 감소시킨 다음 값을 할당하며, 스택에서 튀어나올 때는 그 반대가 됩니다.

참고: 스택의 최상위 포인터는 스택의 최상위 요소와 스택의 최상위 요소 옆에 있는 요소(S.top=0)의 다양한 작업을 가리킵니다.

1. 스택의 최상위 요소

스택으로 푸시:S.data[S.top]=x 스택에서 팝:x=S.data[S.top--]

2. 스택의 최상위 요소의 다음 요소

스택으로 푸시:S.data[S.top]=x 스택에서 팝:x=S.data[--S.top]

3. 스택 비어 있음, 스택 가득 참의 판단 조건도 변경됩니다.

3. 스택 체인 보관 구조

1. 장점: 여러 스택의 저장 공간 공유를 용이하게 하고, 효율성을 향상시키며, 스택 오버플로를 방지합니다.

2. 특징: 모든 작업은 테이블의 헤드에서 수행됩니다. 일반적으로 헤드 노드가 없습니다. 헤드 포인터는 노드 삽입/삭제를 용이하게 하기 위해 스택의 최상위 포인터로 사용됩니다.

4. 스택 팝 시퀀스

1. 팝 시퀀스의 각 요소 뒤에는 그보다 작은 모든 요소가 감소하는 계열을 형성합니다.

증가하는 시퀀스의 경우

2.f(n)=

f(2)=2, f(3)=5, f(4)=14

질문 요약

1. 오류가 발생하기 쉬움

1. 스택과 큐는 저장 구조가 아닌 동일한 논리 구조를 가짐

선형 목록, 스택 및 대기열은 모두 선형 구조입니다.

2. 링크드 리스트는 헤드 노드가 없으며 모든 작업이 리스트의 헤드에서 수행되기 때문에 가장 적합하지 않은 링크 스택입니다.

1. 헤드 노드 포인터만 있고 테일 노드 포인터는 없는 단방향 순환 연결 리스트

2. 이유: 노드를 삽입한 후에도 여전히 순환형 단일 연결 리스트로 변환해야 하며, 꼬리 노드를 찾아야 하는데, 이는 O(n) 시간이 걸립니다.

3.해결책

1. 헤드 노드를 사용하는 경우: 스택의 최상위가 첫 번째 노드를 차지하고, 스택 포인터가 헤드 노드를 차지합니다.

2. 선행 노드가 없는 경우: 스택의 맨 위가 두 번째 노드를 차지하고 스택 포인터가 첫 번째 노드를 차지합니다.

3. 둘 다 첫 번째 노드를 변경하지 않고 유지하며 테이블의 꼬리 요소를 찾을 필요가 없습니다.

3. 상단 포인터가 top인 체인 스택(헤드 노드 없이)에 x 노드를 삽입합니다.

x->다음=상단=x;

4. 푸시 시퀀스는 1,2,...,n이고 팝 시퀀스는 P1, P2,...,Pn입니다. P2=3이면 P3의 가능한 값의 개수는 n-1입니다.

1. 당연히 3 이후에는 4, 5,..., n을 얻을 수 있습니다.

2.P1은 1일 수도 있고 P3은 2일 수도 있습니다.

3.P1은 2일 수 있고 P3은 1일 수 있습니다.

4.P1은 4일 수 있고, P3은 1, 3, 4를 제외한 임의의 숫자일 수 있습니다.

5. 재귀적 프로그램을 비재귀적 방식으로 다시 작성할 경우 스택이 적용되지 않을 수 있습니다.

1. 피보나치 수열 반복 계산에는 루프가 하나만 필요합니다.

6. 스택 상단, 대기열 헤드, 꼬리에 있는 포인터의 정의는 고유하지 않습니다. 질문을 주의 깊게 검토하세요.

2. 알고리즘

1. 연결리스트가 중앙 대칭인지 확인

1. 요소의 첫 번째 절반을 순서대로 스택에 푸시합니다. 두 번째 절반을 처리할 때 연결된 목록 요소에 액세스할 때 요소가 동일한지 확인하기 위해 스택에서 요소를 팝합니다.

2. 짝수일 때는 이상이 없으니 주의하세요. 홀수일 때는 중앙 노드를 먼저 건너뛰어야 합니다.

3. 실제 스택은 필요하지 않습니다. 배열을 스택으로 사용하고 작업 포인터 i를 스택의 최상위 포인터로 사용하면 됩니다.

2.큐

1. 큐의 기본 개념

1. 정의: 테이블의 한쪽 끝에서만 삽입이 가능하고 반대쪽 끝에서는 삭제가 허용되는 선형 테이블입니다.

2.기본 조작

2. 큐 순차 저장 구조

1. 대기열 순차 저장

1. 두 개의 포인터: 앞쪽은 대기열의 머리 요소를 가리키고 뒤쪽은 대기열의 꼬리 요소의 다음 위치를 가리킵니다.

2. 초기 상태(팀 비어 있음): Q.front==Q.rear==0

3. 대기열을 입력합니다. 먼저 대기열의 마지막 요소에 값을 보낸 다음 대기열의 마지막 포인터에 1을 추가합니다.

4. Dequeue: 먼저 헤드 요소의 값을 가져온 다음 헤드 포인터에 1을 추가합니다.

5. 거짓 오버플로가 존재합니다.

6.유형 설명

2. 순환 대기열

1. 초기 상태(팀 비어 있음): Q.front==Q.rear==0

2. 전면 포인터를 이동합니다: Q.front=(Q.front 1)%MaxSize

3. 큐 꼬리 포인터를 전진시킵니다: Q.rear=(Q.rear 1)%MaxSize

4. 대기열 길이: (Q.rear MaxSize-Q.front)%MaxSize

5. 비어있는 팀과 꽉 찬 팀을 구별하세요

1. 유닛 1개를 희생하고 팀에 합류하여 유닛 1개 줄이기(공통 사용)

전체 대기열: (Q.rear 1)%MaxSize==Q.front

빈 팀: Q.front==Q.rear

대기열의 요소 수: (Q.rear MaxSize-Q.front)%MaxSize

2. 요소 수를 나타내는 데이터 멤버를 추가합니다: Q.size

3. 태그 데이터 멤버 추가: tag=0 삭제 작업: 대기열이 비어 있고, tag=1 삽입 작업: 대기열이 가득 찼습니다.

3. 순환큐의 운영

3. 대기열 체인 저장 구조

1. 대기열 체인 저장소

1. 유형 설명

2. 헤드 노드가 있는 단일 연결 목록: 통합 삽입 및 삭제 작업

3. 데이터 요소가 크게 변경되는 상황에 적합합니다. 여러 대기열에 대기열 오버플로나 불합리한 스토리지 할당이 없습니다.

2. 체인 큐의 기본 동작

4. 이중 종료 대기열

1. 정의: 양쪽 끝(프론트엔드와 백엔드)이 큐에 들어가고 나갈 수 있도록 하는 큐입니다.

2. 논리적 구조: 선형 구조

3. 제한된 데크 입력

4. 출력 제한 deque

질문 요약

1. 오류가 발생하기 쉬움

1. 체인화된 스토리지 큐를 사용하여 삭제 작업을 수행하는 경우 헤드 및 테일 포인터가 모두 수정될 수 있습니다.

일반적으로 큐의 헤드 포인터만 수정하면 됩니다. 요소가 하나만 있으면 테일 포인터도 수정하면 됩니다.

2. 체인 큐에서 x가 가리키는 요소가 큐에 들어가면 다음 작업을 수행합니다.

1.뒤->다음=x,x->다음=null,뒤=x;

2. x는 큐의 마지막에 삽입되기 때문에 빈(중간 문장)으로 설정해야 하는데, 이는 더 엄격하다.

2. 질문 유형

1. 순환 큐의 초기 및 전체 상태를 확인합니다.

1. 배열 A[0...n-1], 앞쪽은 팀의 선두를 가리키고 뒤쪽은 팀의 꼬리를 가리킵니다. 첫 번째는 A[0]에 저장되어 초기 상황을 묻는 것입니다.

1. 큐에 들어갈 때 앞쪽은 움직이지 않고 뒤쪽 1은 결국 A[0]을 가리킨다. 따라서 초기 전면=0, 후면=n-1

참고: 특정 문제를 처리할 때 몇 가지 특별한 상황(간단한 스케치 그리기)을 사용하여 비어 있는 상황과 가득 찬 상황을 판단할 수 있으며 이는 직접 생각하는 것보다 빠릅니다.

2. 입/출력이 제한된 이중 종단 큐에서 얻을 수 없는 시퀀스를 결정합니다.

1. 4가지 선택사항에 따라 제거방법을 이용하여 하나씩 직접 입력

2. 일반적인 오류 상황: 마지막 대기열은 앞에 있는 두 숫자(2,3,1) 사이에 끼어들 수 없습니다.

3. 스택과 큐의 적용

1. 브래킷 매칭에 스택 적용

1. 생각

1. 빈 스택을 설정하고 괄호를 순차적으로 읽습니다.

2. )인 경우 스택 상단과 쌍을 이루면 스택에서 팝됩니다(또는 불법입니다.

3. ( )인 경우 더 긴급한 새로운 예상으로 스택에 푸시합니다.

4. 알고리즘이 종료되고 스택이 비어 있습니다. 그렇지 않으면 대괄호 시퀀스가 일치하지 않습니다.

2. 표현식 평가에 스택 적용

1. 후위 표현식: 연산자는 괄호 없이 피연산자 뒤에 옵니다.

2. 접미사를 접미사로 변환하는 과정

1. 연산자 우선순위에 따라 모든 연산자와 피연산자에 괄호를 추가합니다. (원래 존재하는 경우 괄호를 추가할 필요가 없습니다.)

2. 해당 괄호 뒤로 연산자를 이동합니다.

3. 브래킷 제거

참고: 접두사 표현식은 연산자를 괄호 앞에 배치하며 나머지는 동일합니다.

3. 접미사 알고리즘 아이디어에 대한 중위

1. 숫자: 접미사 표현에 직접 추가

2. (:인 경우 스택에 푸시

3. )인 경우: (까지 순서대로 후위 표현식에 스택의 연산자를 추가하고 스택에서 (를 삭제합니다.

4. 만약 - */

1. 스택이 비어 있고 스택에 푸시됩니다.

2. 스택의 맨 위는 ( , 스택에 푸시됩니다.

3. 스택 맨 위에 있는 요소의 우선순위보다 높은 우선순위를 스택에 밀어넣는다. [같은 레벨이면 4번도 실행]

4. 그렇지 않으면 [스택 상단의 우선 순위보다 낮거나 같음] 연산자보다 낮은 연산자가 나올 때까지 순서대로 연산자를 팝하거나(또는 스택이 비어 있을 때) 스택에 푸시합니다.

5. 순회가 완료되면 스택이 비어 있지 않으면 모든 요소를 순서대로 팝업합니다.

4. 접미사 계산 표현 과정

1. 표현식의 각 항을 순차적으로 스캔합니다.

2. 피연산자: 스택에 푸시

3. 연산자 <op>: 스택에서 두 개의 피연산자 x와 y를 연속적으로 종료하여 연산 명령 x<op>y를 형성하고 계산 결과를 다시 스택에 푸시합니다.

3. 재귀에서 스택 적용

1. 두 가지 조건

1. 재귀적 표현(recursive body)

2. 경계 조건(재귀 종료)

2. 재귀의 본질: 원래 문제를 속성은 동일하지만 규모가 더 작은 더 작은 문제로 변환할 수 있습니까?

3. 단점: 재귀가 많아 스택 오버플로를 쉽게 일으킬 수 있으며 반복되는 계산이 많아 효율적이지 않습니다.

4. 장점: 코드가 간단하고 이해하기 쉽다

5. 전환: 스택의 도움으로 달성되어야 함

4. 계층 순회에서 큐 적용

5. 컴퓨터 시스템의 큐 적용

1. 호스트와 외부 장치 간의 속도 불일치 문제를 해결합니다.

1. 인쇄 데이터 버퍼를 설정하고, 가득 차면 출력을 일시 중지하고, 다른 작업을 수행하고, 프린터가 요청을 보낼 때까지 기다립니다.

2. 다수의 사용자로 인한 자원 경쟁 문제 해결

1. 각 요청을 시간 순서에 따라 대기열에 배열하고, 매번 대기열의 첫 번째 사용자에게 CPU를 할당합니다.

질문 요약

하위 주제

4. 특수 매트릭스의 압축 저장

1. 배열의 정의(논리적 구조)

2. 어레이의 저장 구조(순차 저장)

1. 두 가지 매핑 방법: 행 우선, 열 우선

3. 행렬의 압축 저장

1. 압축 저장: 동일한 값을 가진 여러 요소는 하나의 공간만 할당하고, 0은 공간을 할당하지 않습니다.

2. 특수 행렬: 다수의 동일한 행렬 요소 또는 0 요소가 규칙적으로 분포됨

1. 대칭행렬

2.삼각행렬

1. 하삼각행렬

2. 상부삼각행렬

3. 삼중대각 행렬

4. 희소 행렬

1. 저장: 0이 아닌 요소와 해당 행과 열을 삼중항(행 레이블, 열 레이블, 값)으로 구성합니다.

2. 단점: 랜덤 액세스 특성 상실

4장 트리와 이진 트리

1.트리의 기본 개념

1. 나무의 정의

2.기본 용어

1. 노드의 정도

노드의 하위 노드 수

2. 나무의 정도

트리에 있는 노드의 최대 차수

3.노드의 깊이

루트 노드에서 시작하여 위에서 아래로 레이어별로 축적됩니다.

4.노드의 높이

리프 노드에서 시작하여 아래에서 위로 레이어별로 축적됩니다.

5. 나무 높이(깊이)

트리의 최대 노드 수준 수

6. 두 노드 사이의 경로

두 노드 사이를 통과하는 노드의 순서

7. 경로 길이

경로를 통과하는 간선의 수

8.주의

트리의 가지는 방향이 지정되어 있고(부모가 자식을 가리킴) 경로는 위에서 아래로 이루어지며 두 자식 사이에는 경로가 없습니다.

3. 나무의 성질

1. 노드 수 = 모든 노드의 차수 1

2. 차수가 m인 트리의 i번째 레벨에는 최대 m^(i-1)개의 노드가 있습니다.

3. 높이가 h인 m-진 트리에는 최대 (m^h-1)/(m-1)개의 노드가 있습니다.

기하급수의 합

2. 이진 트리의 개념

1. 이진트리의 정의와 주요 특징

1. 이진 트리의 정의

1. 하위 트리는 왼쪽과 오른쪽으로 나눌 수 있으며 순서를 임의로 바꿀 수 없습니다.

2. 이진 트리와 2차 순서 트리의 차이점

1. 2차 트리에는 노드가 3개 이상 있으며 이진 트리는 비어 있을 수 있습니다.

2. 2차 순서 트리의 자식의 왼쪽 및 오른쪽 순서는 다른 자식에 상대적입니다. 자식은 왼쪽과 오른쪽을 구별할 필요가 없습니다. 이진 트리의 왼쪽과 오른쪽 순서가 결정됩니다.

2. 몇몇 특수 이진 트리

1. 완전 이진 트리

트리의 각 수준에는 가장 많은 노드가 포함됩니다.

2. 완전한 이진 트리

1. 정의: 각 노드는 전체 이진 트리에 해당하지만 반드시 각 수준에서 가장 많은 노드는 아닙니다.

2. 자연

1. 리프 노드는 가장 큰 두 개의 레이어에만 있습니다.

2. 차수가 1인 노드가 하나만 있는 경우 해당 노드에는 자식만 남게 됩니다.

3. 이진 정렬 트리

1. 왼쪽 하위 트리에 있는 모든 노드의 키가 루트 노드보다 작습니다.

2. 오른쪽 하위 트리에 있는 모든 노드의 키워드가 루트 노드보다 큽니다.

3. 왼쪽과 오른쪽 하위 트리는 각각 이진 정렬 트리입니다.

4.이진 균형 트리

모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 간의 깊이 차이는 1을 초과하지 않습니다.

3. 이진 트리의 속성

1.n0=n² 1

리프 노드 수 = 2차 노드 수 1 (n=n0 n₁ n²=n₁ 2n2 1)

2. n번째 레이어에는 최대 2^(n-1)개의 노드가 있습니다.

3. 높이가 h인 이진 트리에는 최대 2^h-1개의 노드가 있습니다.

4. 완전한 이진 트리의 경우

1. 노드 i의 상위 노드 i/2(경계를 취함)

2. 노드 i의 왼쪽 자식은 2i, 오른쪽 자식은 2i 1

3. 노드 i가 위치한 레벨은 ㏒₂i(take thebound) 1

5. n개의 노드를 갖는 완전한 이진 트리의 높이는 ㏒²n(경계를 벗어남) 1입니다.

2. 이진 트리의 저장 구조

1.순차저장

1. 완전 이진 트리 및 완전 이진 트리에 적합

2. 일반적으로 존재하지 않는 일부 빈 노드가 이진 트리에 추가됩니다.

3. 참고: 배열 첨자 1에서 저장을 시작해야만 위 속성이 충족될 수 있습니다.

프로그램을 작성할 때 무시하기 쉽습니다

4. 트리의 순차적 저장과 이진 트리 구별

1. 트리에서 배열 첨자는 노드 번호이고, 첨자 위의 내용은 노드 간의 관계를 나타냅니다.

2. 이진 트리에서 아래 첨자는 노드 번호와 노드 간의 관계를 모두 나타냅니다.

2. 체인 보관

1. 바이너리 연결 리스트에는 data, lchild, rchild의 세 가지 필드가 있습니다.

2. n개의 노드가 있는 이진 연결 목록에는 단서 연결 목록을 형성하기 위한 n 1개의 빈 링크 필드(루트 노드는 포인터를 사용하지 않음)가 있습니다.

3. 이진 트리 순회 및 단서 이진 트리

1. 이진 트리 순회

1. 선주문 순회

2. 순차 순회

3. 주문 후 순회

순서는 루트 노드를 방문한 시점을 나타냅니다.

4. 재귀적 알고리즘과 비재귀적 알고리즘의 변환(중간)

1. 생각

1. 먼저 (방문하지 않은) 루트 노드의 왼쪽 노드를 모두 스캔하여 하나씩 스택에 푸시합니다.

2. 스택에서 노드(왼쪽 자식이 없거나 이미 방문한 노드)를 팝하고 액세스합니다.

3. 오른쪽 자식을 스캔하여 스택에 밀어 넣습니다.

4. 그런 다음 오른쪽 자식의 왼쪽 노드를 모두 스캔하여 하나씩 스택에 밀어 넣습니다.

5. 스택이 빌 때까지 계속합니다.

2. 알고리즘 구현

3. 비재귀 알고리즘의 실행 효율성은 재귀 알고리즘보다 높습니다.

5. 레벨 순회(큐)

1. 생각

1. 먼저 루트 노드를 대기열에 넣은 다음 대기열에서 빼고 노드에 액세스합니다.

2. 왼쪽 하위 트리가 있으면 왼쪽 하위 트리의 루트 노드를 큐에 추가합니다.

3. 오른쪽 하위 트리가 있으면 오른쪽 하위 트리의 루트 노드를 대기열에 추가합니다.

4. 그런 다음 대기열에서 제거하고 대기열에서 제거 노드를 방문합니다.

5. 대기열이 빌 때까지 반복합니다.

2. 알고리즘 구현

6. 순회 시퀀스에서 이진 트리 구성

1. 예약주문 및 중간주문

1. 선주문: 첫 번째는 루트 노드입니다.

2. 순차: 루트 노드는 두 개의 하위 시퀀스, 즉 앞쪽 왼쪽 하위 트리와 뒤쪽 오른쪽 하위 트리로 나뉩니다.

3. 선주문: 두 개의 하위 시퀀스를 찾고, 각각의 첫 번째 노드도 루트 노드입니다.

2. 포스트오더와 미드오더

후순위의 마지막 노드는 선주문의 첫 번째 노드와 동일합니다.

3. 첫 주문과 마지막 주문은 불가합니다.

2. 단서 이진 트리

1. 기본 개념

1. 목적: 노드의 선행 노드 및 후행 노드 검색 속도를 높이기 위해

2. 규정

1. 왼쪽 하위 트리가 없으면 lchild가 선행 노드를 가리키도록 하고, 오른쪽 하위 트리가 없으면 rchild가 후속 노드를 가리키도록 합니다.

선행 작업과 후속 작업은 특정 순회 방법에 따라 결정됩니다.

2. 현재 포인터가 선행 포인터(1)를 참조하는지 아니면 왼쪽 하위 포인터(0)를 참조하는지를 나타내는 두 개의 플래그 필드를 추가합니다.

3.단서: 전임자와 후임자를 가리키는 포인터

4. 스레딩(Threading): 이진 트리를 특정 순서로 순회하여 스레드 이진 트리로 바꾸는 프로세스입니다.

2.건축

1. 단서의 본질

1. 이진 트리를 한 번 탐색하고 노드의 왼쪽 및 오른쪽 포인터 필드가 비어 있는지 확인합니다. 비어 있으면 선행 및 후속 단서를 가리키도록 변경합니다.

2. 순차 순회 시퀀스에서 첫 번째 노드는 가장 왼쪽 노드이고 마지막 노드는 가장 오른쪽 노드입니다.

3. 전구체 노드

1. 왼쪽 포인터가 단서이고, 가리키는 노드가 선행 노드입니다.

2. 왼쪽 포인터는 왼쪽 자식이고 왼쪽 하위 트리의 가장 오른쪽 노드는 선행 노드입니다.

4. 후임 노드

1. 오른쪽 포인터가 단서이고, 가리키는 노드가 후속 노드입니다.

2. 오른쪽 포인터는 오른쪽 자식이고 오른쪽 하위 트리의 가장 왼쪽 노드는 후속 노드입니다.

2. 스레드 순회 구현

3. 때로는 양방향 단서 연결 목록을 형성하기 위해 단서 연결 목록에 헤드 노드도 추가됩니다.

1.lchild는 루트 노드를 가리키고, rchild는 순차 탐색의 마지막 노드를 가리킵니다.

2. 순서대로 탐색하면 첫 번째 노드 lchild와 마지막 노드 rchild가 헤드 노드를 가리킵니다.

3.트래버스

1. 이진 트리 순회를 위한 비재귀 알고리즘은 단서 이진 트리를 사용하여 구현할 수 있습니다.

1. 중간 순서의 첫 번째 노드 Firstnode(가장 왼쪽 노드)

2. 중간 순서의 후속 노드 Nextnode

2. 알고리즘 구현

4.나무, 숲

1. 트리 저장 구조

1. 부모의 표현

1. 정의: 지속적인 공간 저장, 각 노드는 의사 포인터를 추가하여 배열의 부모 위치를 나타냅니다. 루트 노드 첨자는 0이고 의사 포인터는 -1입니다.

2. 특징: 부모는 빠르게 구할 수 있지만, 자식은 구조물 전체를 횡단해야 합니다.

2. 아동 대표

1. 정의: 단일 연결 리스트를 사용하여 각 노드의 하위 항목을 선형 구조로 연결합니다.

2. 특징: 아이를 부탁할 때는 편리하지만 부모를 부탁할 때는 불편합니다.

3. 자녀의 형제 표기(왼쪽 자녀, 오른쪽 형제)

1. 정의: 왼쪽 포인터는 첫 번째 자식을 가리키고 오른쪽 포인터는 첫 번째 형제를 가리키며 이진 연결 목록이 저장 구조로 사용됩니다.

2. 장점: 트리를 이진 트리로 변환하는 것이 편리하고 자식을 쉽게 찾을 수 있습니다.

3. 단점 : 부모를 지정하기 위해 부모를 추가하면 편리합니다.

2. 나무, 숲, 이진나무의 변환

1. 트리를 이진 트리로 변환

왼쪽 포인터는 첫 번째 자식을 가리키고 오른쪽 포인터는 첫 번째 형제를 가리키며 루트에는 형제가 없고 이진 트리에는 오른쪽 하위 트리가 없습니다.

2. 포리스트를 이진 트리로 변환

각 이진 트리의 루트는 이전 이진 트리의 오른쪽 하위 트리 역할을 합니다.

3. 이진 트리를 포리스트로 변환(고유)

1. 이진 트리의 루트와 왼쪽 하위 트리를 첫 번째 트리의 이진 트리 형태로 사용한 후 트리로 변환(오른쪽 자식이 형제가 됨)

2. 루트의 오른쪽 하위 트리와 왼쪽 자식은 두 번째 트리 역할을 하고, 오른쪽 자식은 세 번째 트리 역할을 합니다.

3. 나무와 숲의 순회

1. 트리의 첫 번째 루트 순회

먼저 루트를 방문한 다음 각 하위 트리를 왼쪽에서 오른쪽으로 순회합니다. 이는 해당 이진 트리의 루트 우선 순회와 동일합니다.

2. 트리의 백루트 순회

각 하위 트리를 왼쪽에서 오른쪽으로 순회한 후 루트를 방문합니다. 이는 해당 이진 트리의 중간 루트 순회와 동일합니다.

3. 사전예약 숲탐험

이진 트리의 루트 우선 순회와 동일

4. 순차적으로 숲을 횡단하세요

이진 트리의 루트 순회와 동일

4. 트리 적용 - 조합 검색

1.3 작업

1.Union(S,Root1,Root2): 두 개의 하위 컬렉션을 병합하고 루트 Root2를 루트 Root1에 연결합니다.

S[루트2]=루트1

2.Find(S,x): 음수가 발견될 때까지 x를 포함하는 트리의 루트를 찾습니다.

동안(s[x]>=0) x=S[x]; x를 반환;

3.Inital(s): 집합 S의 각 요소는 단일 요소만 포함하는 하위 집합으로 초기화됩니다(모든 요소에는 -1 값이 할당됨).

2. 저장 구조: 트리의 부모 표현, 루트 노드의 첨자는 부분 집합 이름, 루트 노드의 부모 노드는 음수, 크기는 부분 집합 노드의 수

5. 트리와 이진트리의 응용

1. 이진 정렬 트리(이진 검색 트리 BST)

1. 정의

1. 왼쪽 하위 트리에 있는 모든 노드의 키가 루트 노드보다 작습니다.

2. 오른쪽 하위 트리에 있는 모든 노드의 키워드가 루트 노드보다 큽니다.

3. 왼쪽과 오른쪽 하위 트리는 각각 이진 정렬 트리입니다.

중위 순회는 증가하는 순서의 시퀀스를 얻을 수 있습니다.

2. 찾기

1. 비재귀적 구현, 재귀는 간단하지만 비효율적입니다.

3.삽입

1. 새로 삽입되는 노드는 리프 노드여야 합니다. (트리가 비어 있을 때만 삽입됩니다.)

4.건축

1. 삽입된 요소가 동일하지만 순서가 다르더라도 구성되는 BST는 달라집니다.

5.삭제

1. 리프 노드: 직접 삭제

2.i에는 왼쪽/오른쪽 하위 트리가 하나만 있습니다. i의 하위 트리가 i의 상위 노드의 하위 트리가 되어 i의 위치를 대체합니다.

3. i는 왼쪽과 오른쪽에 두 개의 하위 트리가 있습니다. i를 i의 직접적인 후임/전임자로 순서대로 바꾼 다음 직접 후임/전임자를 삭제하고 사례 1,2로 변환합니다.

6. 검색 효율성 분석

1. 평균 검색 길이 ASL = (각 레이어 수 * 해당 레이어 수) / 총 수

2. 최악의 경우: 순서가 지정된 단일 연결 리스트 O(n)과 유사

3. 최선의 경우: 균형 이진 트리 O(㏒₂n)

4. 검색 프로세스: 이진 검색과 유사하지만 이진 검색의 의사결정 트리는 고유합니다.

2. 균형 이진 트리(AVL 트리)

1. 정의

1. 균형 이진 트리: 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이의 절대값은 1을 초과하지 않습니다.

2. 균형 인자: 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이 -1,0,1

2. 삽입(먼저 삽입한 후 조정)

1. 각 조정의 대상은 최소 불균형 하위 트리입니다.

2.LL 균형 회전(오른쪽 단일 회전)

0.A는 최소 불균형 하위 트리의 루트 노드입니다. A를 명확하게 찾으세요.

1. 이유: 새 노드(왼쪽 또는 오른쪽일 수 있음)가 B의 왼쪽 하위 트리 L, A의 왼쪽 하위 트리에 삽입되고 A가 루트인 하위 트리는 균형이 맞지 않습니다.

2.방법

1. A의 왼쪽 하위 B를 오른쪽 위쪽으로 회전하고 A를 루트 노드로 바꿉니다.

2.A는 오른쪽 아래로 회전하여 B의 오른쪽 하위 트리의 루트 노드가 됩니다.

3. 원래 B의 오른쪽 하위 트리가 A의 왼쪽 하위 트리로 사용됩니다.

3.RR 균형 회전(왼쪽 단일 회전)

4.LR 균형 회전(먼저 왼쪽, 그 다음 오른쪽으로 이중 회전)

1. 이유: 새 노드(왼쪽 또는 오른쪽일 수 있음)가 A의 왼쪽 자식 B의 오른쪽 하위 트리 c에 삽입되고 A가 루트인 하위 트리는 균형이 맞지 않습니다.

2.방법

1. A의 왼쪽 자식 B의 오른쪽 하위 트리의 루트 노드 c를 왼쪽으로 회전하고 B 노드 위치까지 회전합니다.

2. 그런 다음 c 노드를 오른쪽 위쪽으로 회전시켜 A 노드 위치로 올립니다.

5.RL 균형 회전(오른쪽 및 왼쪽 이중 회전)

3. 찾기

1. n개의 노드를 포함하는 균형 이진 트리의 최대 깊이는 O(㏒2n)이고, 균형 탐색 길이는 O(㏒2n)이다

3. 허프만 트리와 허프만 코딩

1. 정의

1. 노드의 WPL(Weighted Path Length)

루트 노드에서 임의의 노드까지의 경로 길이(에지 수)와 노드의 가중치를 곱한 값

2. 트리의 가중 경로 길이

모든 리프 노드의 가중치 경로 길이의 합

3. 허프만 트리(최적 이진 트리)

최소 가중치 경로 길이를 갖는 이진 트리

2.건축

1. 건설 과정

1. 가중치가 가장 작은 두 노드를 선택하여 새 노드를 구성합니다. 가중치는 두 노드의 합입니다.

2. 그런 다음 가중치가 가장 작은 나머지 노드를 선택하고 새 노드로 구성한 후 프로세스를 반복합니다.

2.특징

1. 초기 노드는 모두 리프 노드입니다. 가중치가 작을수록 루트 노드까지의 경로 길이가 길어집니다.

2. n-1개의 새 노드, 총 2n-1개의 노드 생성

3. 1차 노드가 없습니다.

3. 허프만 코딩

1. 고정 길이 인코딩

각 문자에 대해 동일한 길이의 이진 표현을 사용하십시오.

2. 가변 길이 인코딩

길이가 다른 이진 비트를 사용하여 다른 문자를 나타냅니다.

3. 접두사 인코딩

인코딩 없음은 다른 인코딩의 접두사입니다.

4.허프만 코딩 과정

루트 노드에서 문자까지의 경로에 표시된 시퀀스, 0은 왼쪽 자식으로 이동, 1은 오른쪽 자식으로 이동

5장 그림

1. 그래프의 기본 개념

1. 그래프의 정의

0.G=(V,E),V(G): 비어 있지 않은 유한 정점 집합 E(G): 가장자리 집합 |V|: 정점 수(그래프 순서) |E|: 가장자리 수

0.1 참고: 선형 테이블은 빈 테이블일 수 있고 트리는 빈 트리일 수 있지만 그래프는 빈 그래프일 수 없습니다. 꼭지점 세트는 비어 있지 않아야 하며 에지 세트는 비어 있을 수 있습니다.

1. 방향성 그래프

<v,w>: v에서 w까지의 호(v는 w에 인접함/w는 v에 인접함) v: 호 꼬리 w: 호 머리

2. 무방향 그래프

(v,w)=(w,v)

3. 간단한 다이어그램

중복된 가장자리가 없으며 정점에서 자체까지의 가장자리가 없습니다.

4.다중 그래프

중복된 모서리가 있고 꼭지점에서 자체 모서리까지의 모서리가 있습니다.

5. 전체 그래프(간단한 전체 그래프)

1. 무방향 완전 그래프: 임의의 두 정점 사이에 n(n-1)/2개의 간선이 있습니다.

2. 방향성 완전 그래프: 임의의 두 꼭지점은 반대 방향으로 두 개의 호를 가집니다. n(n-1)

6. 하위 사진

하위 그래프 생성: 동일한 정점 세트가 있는 하위 그래프

7. 연결형, 연결형 그래프, 연결형 구성요소(무방향 그래프)

1. 최대로 연결된 하위 그래프(연결된 구성 요소): 연결된 하위 그래프에는 반드시 모든 정점이 아닌 모든 간선이 포함됩니다(연결된 그래프일 필요는 없음).

2. 최소 연결 서브 그래프: 간선 수를 최소화하면서 그래프 연결성을 유지하는 서브 그래프(단일 정점일 수 있음)

측면을 기준으로 한 최소, 최대

8. 강하게 연결된 그래프, 강하게 연결된 구성요소(유향 그래프)

9. 스패닝 트리, 스패닝 숲

1. 연결된 그래프의 스패닝 트리, 모든 정점을 포함하는 최소 연결 하위 그래프(n개의 정점에는 n-1개의 모서리가 있음)

2. 연결되지 않은 그래프에서는 연결된 구성 요소의 스패닝 트리가 연결되지 않은 그래프의 스패닝 포리스트를 구성합니다.

10. 정점 각도, 내부 각도, 외부 각도

1. 꼭지점의 차수: 꼭지점을 끝점으로 하는 모서리의 수

1. 노드의 정도

노드의 하위 노드 수

2. 무방향 그래프에서: 모든 꼭지점의 각도의 합 = 모서리 수 * 2

3. 유향 그래프에서: 정점의 차수 = 진입 차수와 진출 차수, 모든 정점의 진입 차수 합 = 진출 차수의 합 = 간선 수

11. 오른쪽 측면, 네트

1. 가중치 사진(그물) : 측면에 가중치가 있는 사진

12.밀도 그래프, 희소 그래프

13. 경로, 경로 길이, 루프

1. 루프/루프: 첫 번째 정점과 마지막 정점이 동일한 경로

14. 간단한 경로, 간단한 루프

1. 단순 경로: 정점이 반복적으로 나타나지 않는 경로

2. 단순 루프: 첫 번째 꼭지점과 마지막 꼭지점을 제외하고 다른 꼭지점은 반복해서 나타나지 않습니다.

15. 거리

1. v에서 w까지의 최단 경로가 존재하면 거리로, 존재하지 않으면 무한대로 기록된다.

16. 방향성 트리

1. 한 꼭지점의 진입차수가 0이고 다른 꼭지점의 진입차수가 1인 유향 그래프입니다.

2. 사진 저장 및 기본 동작

1. 인접 행렬 방식(순차적)

1. 정의

1. 1차원 배열은 정점 정보를 저장하고, 2차원 배열은 모서리 정보를 저장합니다.

2.특징

1. 무방향 그래프/유방향 그래프: i번째 행에 있는 0이 아닌 요소의 개수는 i번째 꼭지점의 차수/외차수입니다.

2. 모서리가 있는지 확인하는 것은 쉽지만 모서리가 몇 개 있는지 확인하는 것은 어렵습니다.

3. 조밀한 그래프는 인접 행렬을 사용하는 데 적합합니다.

4.Aⁿ[i][j]: 정점 i에서 정점 j까지 길이 n인 경로의 수

2. 인접 목록 방법(링크)

1. 정의

1. 순차 저장소와 연결 저장소를 결합하여 각 정점 i에 대한 단일 연결 목록을 만듭니다.

2. 정점 테이블: 첫 번째 인접 목록(firstarc)에 대한 정점 필드(데이터) 포인터

3. 에지 테이블: 인접 포인트 필드(adjvex) 다음 인접 리스트를 가리키는 포인터 필드(nextarc)

2.특징

1. 무방향 그래프: 저장 공간 O(|V| 2|E|) 유방향 그래프: O(|V| |E|)

2. 희소 그래프의 공간을 절약하기 위해 인접 목록 방법을 사용합니다.

3. 교차 연결 리스트(유향 그래프)

1.정의: 방향성 그래프의 체인 저장소

2. 구조

1. ArcNode: 도메인 5개

1. 테일 도메인(tailvex), 헤드 도메인(headvex): 호 테일과 호 헤드를 나타냅니다.

2. 체인 도메인 hlink, tlink: 동일한 호 머리/호 꼬리를 가진 다음 호를 나타냅니다.

<v,w>: v에서 w까지의 호(v는 w에 인접함/w는 v에 인접함) v: 호 꼬리 w: 호 머리

3.info 필드: 아크 관련 정보

2. 정점 포인터(VNode): 3개 필드

1.데이터 필드: 정점 데이터 정보(정점 이름)

2. Firstin 도메인, Firstout 도메인: 이 정점을 호 머리/호 꼬리의 첫 번째 노드로 사용합니다.

3. 참고: Vertex 노드는 순차적으로 저장됩니다.

3.특징

1. vi가 꼬리인 호와 머리가 vi인 호를 쉽게 찾을 수 있습니다. 정점의 아웃/인 각도를 쉽게 찾을 수 있습니다.

2. 고유하지 않지만 그래프를 결정한다는 의미입니다.

4. 인접 다중 목록(무방향 그래프)

1.정의: 무방향 그래프의 또 다른 체인 스토리지

2. 구조

1. 각 에지는 노드로 표현됩니다.

1.mark 플래그 필드: 이 에지가 검색되었는지 여부

2.ivex,jvex: 그래프의 모서리에 연결된 두 정점의 위치

3.ilink,jlink: 정점 ivex/jvex에 연결된 다음 가장자리를 가리킵니다.

4.info: 다양한 정보에 대한 포인터 필드

2. 정점은 노드로 표현됩니다.

1.데이터 필드: 정점 관련 정보

2.firstedge domain: 정점에 붙은 첫 번째 edge

3.특징

1. 동일한 정점에 연결된 Edge는 동일한 Linked List로 연결되며, 각 Edge 노드는 동시에 두 개의 Linked List로 연결됩니다.

2. 각 에지에는 노드가 하나만 있습니다.

5. 그래프의 기본 동작

1. 그래프의 저장 구조에 관계없이 저장 방법에 따라 성능이 다릅니다.

2. 특정 작업

3. 그래프 순회

1. 너비 우선 탐색(BFS)

1. 정의

이진 트리와 유사한 계층적 순회 알고리즘으로, 가장 먼저 발견된 노드에 우선순위를 부여합니다.

2. 생각

1. 먼저 시작 정점 v를 방문합니다.

2. v의 방문하지 않은 모든 인접 정점을 순차적으로 방문합니다.

3. 그런 다음 이 정점에서 시작하여 방문하지 않은 모든 노드를 방문합니다.

3. 알고리즘 설명

1. 계층적 검색, 앞으로 노드 배치에 액세스, 뒤로 상황이 있는 깊이 우선과 달리 재귀적이지 않음

2. 대기열 보조 표시 배열을 사용합니다(정점 방문 여부).

3. 알고리즘 구현

4.성능 분석

1. 공간 복잡도: O(|V|)

보조 대기열의 도움으로 정점은 한 번만 대기열에 추가됩니다.

2. 시간 복잡도

1. 인접 목록: O(|V| |E|)

2. 인접 행렬: O(|V|²)

그래프 탐색의 본질: 각 꼭지점에 대해 인접한 점을 찾는 과정

5.BFS는 단일 소스 최단 경로 문제를 해결합니다.

5. 너비 우선 스패닝 트리

1. 정의: 너비 순회 중에 얻은 순회 트리

2. 특징: 인접 행렬에서는 고유하지만 인접 목록에서는 고유하지 않습니다.

DFS도 마찬가지다.

2. 깊이 우선 탐색(DFS)

1. 정의

트리의 선주문 순회와 유사하게 마지막으로 발견된 노드에 우선순위가 부여됩니다.

2. 생각

1. 먼저 시작 정점 v를 방문합니다.

2. v의 방문하지 않은 인접한 정점 w를 방문합니다.

3. 그런 다음 w의 방문하지 않은 인접 정점 w2를 방문합니다.

4. 더 이상 아래쪽으로 접근할 수 없을 때까지 반복하고 가장 최근에 방문한 정점으로 차례로 돌아갑니다.

3. 알고리즘 설명

1. 재귀적 형태를 사용하여 정점에서 시작

2. 알고리즘 구현

4.성능 분석

1. 공간 복잡도: O(|V|)

재귀 작업 스택 사용

2. 시간 복잡도

1. 인접 목록: O(|V| |E|)

2. 인접 행렬: O(|V|²)

5. 깊이 우선 스패닝 트리/포리스트(비연결 그래프)

3. 그래프 순회 및 그래프 연결성

1. 무방향 그래프

1. 연결됨: 한 번의 순회에서 모든 정점을 방문합니다.

2. 비연결(Non-connected): 한 번의 순회로 연결된 구성요소의 모든 정점을 방문합니다.

2. 방향성 그래프

1. 초기 정점부터 각 정점까지의 경로가 있으면 모든 정점에 접근할 수 있고 그렇지 않으면 접근할 수 없다.

3. 두 번째 for 루프가 알고리즘에 추가된 다음 초기 점이 선택됩니다.

첫 번째 for 루프는 정점을 FLASE로 초기화합니다.

4. 무방향 그래프: BFS 또는 DFS에 대한 호출 수 = 그래프의 연결된 구성 요소 수

4. 다이어그램의 적용

1. 최소 스패닝 트리(MST)

1. 정의

간선 가중치의 합이 가장 작은 스패닝 트리

2.특징

1. 트리 모양은 고유하지 않으며 간선 가중치의 합은 고유합니다.

2. 모서리 수 = 정점 수 - 1

3. 일반적인 생각

T가 스패닝 트리를 형성하지 않는 경우 최소 비용 가장자리를 찾고 T를 추가한 후 루프가 생성되지 않습니다.

4. 두 가지 알고리즘

1.프림 알고리즘(Prim)

1. 생각(정점에서 확장)

1. 초기화: 먼저 임의의 정점을 초기 정점으로 선택합니다.

2. 루프(모든 정점이 포함될 때까지): 그런 다음 이 정점의 인접한 가장자리 중에서 가중치가 가장 작은 가장자리를 선택하고 순환을 형성하지 않습니다.

3. 그런 다음 루프를 형성하지 않는 두 정점의 인접한 가장자리 중 가중치가 가장 작은 가장자리를 선택합니다.

2.특징

1. 시간 복잡도: O(|V|²), |E|에 의존하지 않음, 조밀한 간선이 있는 그래프에 적합

2.크루스칼 알고리즘(Kruskal)

1. 생각(체중 증가)

1. 초기화: 먼저 모든 정점을 포함하고 가장자리는 포함하지 않습니다.

2. 루프(트리가 될 때까지): n-1개의 Edge가 포함될 때까지 순환을 형성하지 않고 가중치가 증가하는 순서대로 Edge를 선택합니다.

2.특징

1. 힙을 사용하여 O(|E|log|E|)의 시간 복잡도로 간선 세트를 저장합니다. 이는 간선이 희박하고 정점이 많은 그래프에 적합합니다.

2. 최단 경로

1. 단일 소스에서 최단 경로를 찾는 Dijkstra 알고리즘

1. 보조변수

1. Set S: 발견된 최단 경로의 정점을 기록하며, 초기값은 0이다.

2.dist[]: 소스 지점 v0에서 다른 정점까지의 현재(지속적으로 업데이트되는) 최단 경로 길이를 기록합니다. 초기 값은 arcs[v0][i]입니다.

3.path[]: path[i]는 소스 지점에서 i까지의 최단 경로의 선행 노드이며, 그 값은 v0에서 vi까지의 최단 경로로 역추적될 수 있습니다.

2. 생각

1. 초기화: 집합 S는 {0}이고 dist[]는 초기 정점 0에서 각 정점까지의 거리이며 무한대는 없습니다. path[]의 초기 정점 0은 -1(항상 변경되지 않음)이고, 0에서 다른 점까지의 거리는 0이고, 0에서 다른 점까지의 거리는 무한대입니다.

2. dist[]에 남은 값이 가장 작은 점 j를 선택합니다. dist[j] arcs[j][k]<dist[k]이면 dist[k]를 업데이트합니다. 이 점을 집합 S에 추가합니다. dist[k]가 업데이트되면 path[k]=j로 둡니다.

3. S가 모든 포인트를 포함할 때까지 세트 S의 나머지 포인트에 대해 작업을 반복합니다.

3.특징

1. 단일 소스의 시간 복잡도는 O(|V|²)이고, 모든 노드 쌍의 시간 복잡도는 O(|V|3)입니다.

2. 가장자리에 음의 가중치가 있는 경우 알고리즘이 적용되지 않습니다.

2.플로이드 알고리즘은 정점 사이의 최단 경로를 찾습니다.

1. 생각

1. A﹣1에서 시작하여 Aⁿ﹣1까지 n차 정사각 행렬 시퀀스를 반복적으로 생성합니다.

행렬 위첨자와 괄호

2. 초기: 두 정점 사이에 가장자리가 있으면 가중치는 최단 경로로 간주됩니다. 가장자리가 없으면 무한합니다.

3. 나중에 정점 k(0에서 n-1까지의 k)를 원래 경로에 중간 정점으로 점진적으로 추가합니다. 경로가 감소하면 원래 경로를 교체합니다.

4.A(k)[i][j]: 정점 i에서 정점 j까지, 중간 노드 수가 k보다 크지 않은 최단 경로의 길이

2.특징

1. 시간 복잡도: O(|V|³)

2. 음의 가중치를 갖는 간선은 허용되며, 음의 가중치를 갖는 간선은 루프를 형성하는 것이 허용되지 않습니다.

3. 왕복 이중 모서리가 있는 유향 그래프로 간주되는 가중치 무향 그래프에 적용 가능

3.위상적 정렬

1. 방향성 비순환 그래프(DAG 그래프)

유방향 그래프에는 순환이 없습니다.

2. 정점은 활성 네트워크(AOV 네트워크)를 나타냅니다.

DAG 그래프는 프로젝트를 나타내고, 꼭짓점은 활동을 나타내며, 방향이 있는 모서리 <vi, vj>는 활동 i가 활동 j보다 앞에 있어야 함을 나타냅니다.

3. 토폴로지 정렬(DAG 그래프)

1. 정의

1. 각 정점은 한 번만 나타납니다.

2. A가 B보다 앞에 있으면 B에서 A로 가는 경로가 없습니다.

2. 시행방법

1. DAG 그래프에서 선행자가 없는 정점을 선택하여 출력한다.

2. 정점과 정점에서 시작하는 모든 방향 가장자리를 삭제합니다.

3. 그래프가 비어 있을 때까지/전임자가 없는 노드가 없을 때까지(그래프에 사이클이 있어야 함) 1단계와 2단계를 반복합니다.

3.특징

1. 시간 복잡도 O(|V| |E|)

가장자리를 제거하는 동안 정점 출력

4.주의

1. 프로젝트는 각도가 0인 정점에서 시작할 수 있습니다.

2. 꼭짓점에는 여러 개의 직접 후속 항목이 있으며 결과는 일반적으로 고유하지 않습니다.

3. 인접행렬은 삼각행렬이고 위상정렬(topological sorting)이 있으나 반드시 그 반대의 경우는 아니다. 정렬결과에 따라 정점번호를 재배열할 수 있으며 인접행렬은 삼각행렬이다.

4. 임계 경로

1. 에지를 사용하여 활성 네트워크(AOE 네트워크)를 나타냅니다.

1. 정의

꼭짓점은 이벤트를 나타내고, 방향이 있는 간선은 활동을 나타내며, 가중치는 비용(시간)을 나타냅니다.

2. 두 가지 속성

1. 꼭지점으로 표현되는 이벤트가 발생한 후, 꼭지점에서 시작하여 방향성 에지로 표현되는 활동이 시작될 수 있습니다.

2. 유향 엣지로 표현되는 모든 활동이 특정 꼭지점 끝으로 진입해야만 꼭지점이 표현하는 이벤트가 발생할 수 있다.

2. 여러 개념

1. 시작 정점(소스 포인트): 전체 프로젝트의 시작인 차수가 0인 정점이 하나만 있습니다.

2. 끝 정점(싱크): 아웃 차수가 0인 정점이 하나만 있으며, 이는 전체 프로젝트의 끝입니다.

3. 임계 경로(Critical Path): 경로 길이가 최대인 경로

4. 중요 활동: 중요 경로에 있는 활동

5. 최소 시간: 임계 경로의 길이

3. 여러 매개변수

1. 이벤트 vk의 가장 빠른 발생 시간 Ve(k)

1. 정의: 정점 V에서 Vk까지의 가장 긴 경로 길이는 Vk에서 시작하는 모든 활동의 가장 빠른 시작 시간을 결정합니다.

2. 찾는 방법: 근원지점부터 거꾸로 가중치를 더하고, 서로 다른 경로의 최대값을 취한다.

이벤트가 시작되기 전에 모든 활동을 완료해야 합니다.

2. 이벤트 vk의 최근 발생 시간 Vl(k)

1. 정의: 전체 프로젝트의 완료를 지연시키지 않고 이 시간이 발생하는 가장 늦은 시간

2. 찾는 방법: Vl(싱크 포인트) = Ve(싱크 포인트), 싱크 포인트 앞쪽에서 가중치를 빼고, 서로 다른 경로의 최소값을 취함

전체 프로젝트가 지연되지 않도록 최소값을 취하십시오.

3. 활동 ai의 가장 빠른 발생 시간 e(i)

1. 정의 : 활동의 시작점으로 나타나는 사건의 가장 빠른 발생시간

2. 찾는 방법: <Vk, Vj>는 활동 ai를 나타내고 e(i)=Ve(k)

4. 활동 ai의 최근 발생 시간 l(i)

1. 정의 : 활동의 종료시점으로 표시되는 사건의 가장 최근 발생시간과 활동에 소요되는 시간의 차이

2. 찾는 방법: <Vk,Vj>는 활동 ai,l(i)=Vl(j)-Weight(Vk,Vj)를 나타냅니다.

5. 활동의 차이 d(i)=l(i)-e(i)

4. 임계 경로

모든 활동 중 d()=0의 차이가 있는 활동이 주요 경로를 구성합니다.

제6장 검색

1. 검색의 기본 개념

1. 조회 테이블(조회 구조): 조회에 사용되는 데이터 수집

2. 정적 조회 테이블에 적합: 순차 검색, 절반 검색, 해시 검색

3. 동적 조회 테이블에 적합합니다. 이진 정렬 트리, 해시 검색, 이진 균형 트리 및 B-트리는 모두 이진 정렬 트리를 개선한 것입니다.

4. 평균 검색 길이(ASL)

2. 순차검색과 이진검색

1. 순차검색(선형검색)

1. 일반 선형 테이블의 순차 검색

1. 알고리즘 특성

1. 센티넬(배열의 첫 번째 요소)을 도입하고 뒤에서 앞으로 검색합니다. 배열이 경계를 넘을지 여부를 판단할 필요가 없으므로 프로그램 효율성이 향상됩니다.

2. 장점과 단점

1. 단점 : n이 크면 효율이 낮다.

2. 장점: 데이터 요소 저장에 대한 요구 사항과 질서에 대한 요구 사항이 없습니다.

3.성능

1.ASL 성공=(n 1)/2

2.ASL 실패=n 1

보초 추가

2. 정렬된 목록에서 순차적 검색

1. 의사결정 트리: 원형 노드는 존재 노드, 직사각형 노드는 실패 노드(간격), n개의 성공은 n개의 실패 노드를 가져야 함

2. 실패한 노드에 도달하기 위한 검색 길이 = 그 위에 있는 원형 노드의 레이어 수

3. ASL 실패만 다름 = (1 2 ... n n)/n 1

마지막 두 개의 실패한 노드는 동일한 레벨에 있으며 둘 다 n입니다.

2. 반검색(이진검색)

1. 알고리즘 특성

1. 루프 조건: low≤high는 결국 모두 동일한 값을 가리키도록 보장합니다. 그렇지 않으면 검색할 숫자가 하나 줄어듭니다.

2.mid=(low high)/2는 경계를 제거하는 것과 같습니다.

2.성능

1. 시간복잡도 : O(log2n)

2.ASL: 레이어당 레이어 수 * 레이어당 노드 수 / 요약 포인트 수, n 레이어에는 2ⁿ﹣¹ 노드가 있습니다.

3. 블록 검색(인덱스 순서 검색)

1. 알고리즘 특성

1. 순차탐색과 이진탐색의 각각의 장점을 흡수하고 동적인 구조를 가지며 빠른 탐색에 적합하다.

2. 생각

1. 여러 개의 하위 블록으로 나누어 블록의 순서를 취소할 수도 있고 블록의 순서를 지정할 수도 있습니다.

2. 첫 번째 블록의 가장 큰 키워드 < 두 번째 블록의 모든 레코드 등

3. 각 블록의 가장 큰 키워드와 각 블록의 첫 번째 요소의 주소를 키워드 순서로 포함하는 인덱스 테이블을 생성합니다.

3. 검색과정

1. 인덱스 테이블에서 블록을 결정하고 순차적으로/반씩 검색합니다.

2. 블록 내에서 순차적으로 검색

4.성능

ASL=인덱스 테이블 ASL 블록 내 ASL

질문 요약

1. 오류가 발생하기 쉬움

1. 이제 절반 검색 속도가 일반적으로 빨라졌습니다. 특별한 경우에는 순차 검색이 더 빨라질 수 있습니다.

2. 이진 검색과 이진 정렬 트리의 시간 성능

1. Half Search는 Binary Decision Tree로 측정되며 ASL은 항상 O(log2n)입니다.

2. 이진 정렬 트리는 데이터의 입력 순서와 관련이 있으며 최악의 경우는 O(n)입니다.

3. 반으로 검색할 경우 중간값에 경계가 있음

2.공식

1. 이진 의사결정 트리의 높이: ┎log2(n 1)┒ 또는 ┕log2n┙ 1

1. 높이 차이가 최대 1인 균형 잡힌 이진 트리입니까, 아니면 이진 정렬 트리입니까?

2. 실패한 노드의 비교 횟수(차이는 1을 초과하지 않음)/최대 비교 횟수

3. 총 노드 수 n=2^h-1

2. n 레코드의 인덱스 시퀀스 테이블의 최적 블록 길이:

모두 순차적으로 탐색하며, 블록 길이는 b, 인덱스 테이블 ASL=(n/b 1)/2, 블록 내 ASL=(b 1)/2, 기본 부등식을 덧셈에 사용한다.

3. 순차 검색 ASL=(n 1)/2, 인덱스 검색 ASL=인덱스 테이블 ASL 블록 내 ASL

3. 질문 유형

1. 트리가 이진 검색 결정 트리인지 확인

비교할 마지막 노드(트리의 중간 위치)를 가져와 상한과 하한이 일치하는지 확인합니다. (루트 노드에서 먼저 상한과 하한을 결정할 수도 있습니다.)

2. 순서가 지정된 목록에서 블록 검색과 유사한 아이디어를 직접 사용: W252

블록 내 검색 길이는 세그먼트마다 다릅니다.

4.지식 포인트

1.k-point 탐색 방법: 성공과 실패의 시간복잡도는 O(logk(n))

n 노드가 있는 k-진 트리의 깊이는 ┕logk(n)┙ 1입니다.

2. 검색 확률이 다를 때 가장 효과적인 방법은 순차 검색을 이용하는 것입니다.

검색 확률이 높은 순서대로 정렬

3.B-트리와 B-트리

1.B-트리와 기본 동작

1. 정의

0.B-트리(모든 노드에 대해 균형 인자가 0인 다중 경로 균형 검색 트리), 최대 하위 노드 수는 B-트리의 순서(m)입니다.

1. 각 노드에는 최대 m개의 하위 트리(최대 m-1개의 키워드)가 있습니다.

2. 루트 노드가 터미널 노드가 아닌 경우 하위 트리가 2개 이상, 키워드가 1개 이상 존재

3. 루트 노드를 제외한 모든 비리프 노드에는 최소 ┎m/2┒ 하위 트리와 최소 ┎m/2┒-1 키워드가 있습니다.

4. 모든 리프가 아닌 노드 구조

1. 키워드는 오름차순으로 정렬됩니다.

2. 왼쪽 하위 트리의 모든 숫자 <키워드에 해당, 오른쪽 하위 트리의 모든 숫자>가 키워드에 해당

5. 모든 리프 노드는 정보 없이 동일한 수준에 있습니다(외부 노드/실패 노드).

2.나무 B의 높이

1. 최소 높이

각 노드에는 최대 m개의 하위 트리와 m-1개의 키워드가 있습니다.

h≥logm(n 1) n≤(m-1)(1m m² ... m^(h-1))=m^h-1

2. 최대 높이

첫 번째 레이어는 적어도 하나의 노드를 갖고, 두 번째 레이어는 적어도 2개의 노드를 갖고, 세 번째 레이어는 적어도 2┎m/2┒,..., 그리고 h 첫 번째 레이어는 적어도 2┎m/2┒^를 갖습니다. (h-1) 노드.

h1번째 레이어는 리프 노드(실패 노드)이고, 수는 n 1(간격 수)이며, n 키워드에 대해 n-1 개의 실패 노드가 있습니다.

n 1≥2┎m/2┒^(h-1)

3.B-트리 검색

이진 검색 트리와 유사

4.B-트리에 삽입

1. 포지셔닝: 가장 낮은 수준의 리프가 아닌 노드에 삽입되어야 합니다.

2.삽입

1. 장애가 발생하지 않은 각 노드의 키워드 수는 [┎m/2┒-1,m-1] 이내입니다.

2. 삽입 후 키워드 개수가 <m이면 직접 삽입 >m-1, 노드를 분할합니다.

3. 분할방법

1. 키를 중간 위치 ┎m/2┒에서 두 부분으로 나누어 원래 노드를 나눕니다.

2. 중간 위치의 ┎m/2┒ 노드가 상위 노드에 삽입되고, 왼쪽과 오른쪽 부분이 왼쪽과 오른쪽 하위 트리로 사용됩니다.

3. 상위 노드도 상한을 초과하는 경우 루트 노드에 도달할 때까지 계속 분할합니다. B-트리 높이는 1입니다.

5.B-트리 삭제

1. 터미널 노드에서

1. 키워드 직접 삭제

키워드 수>┎m/2┒-1

2. 형제이면 충분하다

1. 키워드 수 = ┎m/2┒-1이고, 인접한 오른쪽(왼쪽) 형제 노드의 키워드는 >┎m/2┒입니다.

2. 부모-자식 전치 방법: 부모 노드 중 하나가 삭제된 노드에 들어가고, 형제 노드 중 하나가 부모 노드에 들어갑니다.

3. 형제가 부족하여 빌릴 수 없음(합병 방식)

1. 키워드 수 = ┎m/2┒-1, 인접한 오른쪽(왼쪽) 형제 노드의 키워드 = ┎m/2┒-1

2. 병합 방법: 부모 노드 중 하나를 형제 노드 중 하나와 병합하여 삭제된 노드를 대체합니다.

3. 상위 노드가 루트 노드이고 0으로 줄어들면 루트 노드를 직접 삭제하고 병합 후 새 노드가 루트가 됩니다.

4. 상위 노드는 루트 노드가 아니며 ┎m/2┒-2로 축소된 후 형제와 조정 또는 병합(충분할 때 먼저 빌려옴)

2. 터미널 노드에 없음

1. 왼쪽 하위 트리의 키워드 개수 >┎m/2┒-1이면 k를 k의 선행 노드(왼쪽 하위 트리의 가장 오른쪽 노드)로 교체한 후 k를 재귀적으로 삭제합니다.

2. 오른쪽 하위 트리의 키워드 개수 >┎m/2┒-1이면 k를 k의 후속 노드(오른쪽 하위 트리의 가장 왼쪽 노드)로 교체한 후 k를 재귀적으로 삭제합니다.

3. 좌우 하위 트리의 키워드 개수 = ┎m/2┒-1이면 두 하위 트리를 직접 병합하고 k를 직접 삭제

2.B-트리의 기본 개념

1. 정의

1. 각 분기 노드에는 최대 m개의 하위 트리(하위 노드)가 있습니다.

2. 리프가 아닌 루트 노드에는 하위 트리가 2개 이상 있고, 루트 노드를 제외한 모든 리프가 아닌 노드에는 하위 트리가 ┎m/2┒ 이상 있습니다.

3. 노드의 하위 트리 수 = 키워드 수

B-트리에서: 노드의 하위 트리 수 = 키워드 수 1

4. 모든 리프 노드에는 모든 키워드(순서대로 정렬)와 해당 레코드에 대한 포인터가 포함되며 인접한 리프 노드는 크기에 따라 서로 연결됩니다.

5. 모든 분기 노드(인덱스로 간주될 수 있는 인덱스)에는 각 하위 노드의 키워드 최대값과 하위 노드에 대한 포인터만 포함됩니다.

2.특징

1. 두 개의 헤드 포인터: 하나는 루트 노드를 가리키고 다른 하나는 가장 작은 키워드가 있는 리프 노드를 가리킵니다.

2. 두 가지 검색 작업: 최소 키워드 순서로 검색/루트 노드에서 다방향 검색

3. 참고: 검색 시 리프가 아닌 노드가 지정된 값과 같아도 검색은 종료되지 않습니다. 리프 노드까지 아래쪽으로 계속 검색됩니다. 검색 성공 여부에 관계없이 루트 노드에서 리프 노드까지의 경로입니다.

질문 요약

1. 오류가 발생하기 쉬움

1. 노드의 키워드 수 ≠ 하위 트리 수인 경우 B 트리가 아니어야 합니다.

2. 루트 노드를 제외한 모든 비리프 노드에는 최소 ┎m/2┒ 하위 트리와 최소 ┎m/2┒-1 키워드가 있습니다.

루트 노드에 특별한 주의를 기울이십시오. 최소한 2개의 하위 트리와 1개의 키워드가 있습니다.

3. 삽입 후 B-트리가 분할될 때 루트 노드가 분할되지 않는 한 높이는 1이 되지 않습니다.

2.공식

1. 최소 높이: h≥logm(n 1)

2. 최대 높이: n 1≥2┎m/2┒^(h-1)

3.지식 포인트

1. 3차 B-트리의 경우: 노드 수가 가장 적을 때는 완전 이진 트리와 유사하고, 노드 수가 가장 클 경우 완전 삼항 트리와 유사합니다.

요약 포인트=m^h-1

2.B 트리는 파일 인덱스/데이터베이스 인덱스로 사용됩니다.

4.해시 테이블

1. 해시 테이블의 기본 개념

1. 해시 함수

키워드를 해당 주소에 매핑하는 함수는 Hash(key)=addr(배열 첨자/색인/메모리 주소일 수 있음)로 기록됩니다.

2. 갈등

두 개 이상의 서로 다른 키워드가 동일한 주소에 매핑됩니다.

3.동의어

서로 다른 키워드의 충돌

4.해시 테이블

키워드를 기반으로 직접 접근하는 데이터 구조, 이상적으로는 O(1)

2.해시 함수의 구축 방법

0.주의사항

1. 정의 도메인에는 모든 키워드가 포함되어야 하며, 값 범위는 해시 테이블의 크기/주소 범위에 따라 달라집니다.

2. 주소는 확률이 동일하고 고르게 분포되어야 합니다.

3. 함수를 최대한 간단하게 만들어서 단시간에 계산해 보세요

1. 직접 어드레싱 방식

1. 기능: H(키)=a*키 b

2. 특징: 충돌이 없으며 기본적으로 지속적인 키워드 배포에 적합합니다.

2. 나머지법으로 나누기

1. 기능: H(키)=키%p

2. P의 선택: m(해시 테이블 길이)보다 크지 않지만 m에 가장 가깝거나 같은 소수 p

3. 디지털 분석 방법

1. 상대적으로 균일한 디지털 분포를 갖는 비트 수를 해시 주소로 선택합니다.

2. 특징: 알려진 키워드 모음에 적합

4.사각형의 중심을 찾는 방법

1. 제곱 값의 가운데 숫자를 해시 주소로 사용합니다.

2. 각 비트의 값이 충분히 균일하지 않거나 해시 주소에 필요한 비트 수보다 적은 상황에 적용 가능합니다.

5. 접는 방법

1. 키워드를 같은 자릿수로 여러 부분으로 나누고 중첩 합계를 해시 주소로 사용합니다.

2. 많은 자릿수에 적합하며 각 비트의 자릿수가 대략 균등하게 분포되어 있습니다.

3. 갈등 처리 방법

1. 주소공개법

0. 정의

1. 무료 주소는 동의어와 비동의어 모두에 열려 있습니다.

2. 재귀 수식: Hi=[H(key) di]%m, di: 증분 시퀀스

1. 선형 검출 방법

1.정의: di=0,1,2,...,m-1

2. 특징: 인접한 해시 주소에 많은 수의 요소가 모여 검색 효율성이 떨어집니다.

2. 제곱 검출 방식(2차 검출 방식)

1. 정의: di=0²,1²,-1²,2²,-2²,...,k²,-k²

2.특징

1. 장점: 누적 문제를 피할 수 있습니다.

2. 단점: 세포의 절반만 검출 가능

3.리해싱 방식(이중 해싱 방식)

1. 정의: di=Hash²(키), Hi=[H(키) i*Hash²(키)]%m

i는 충돌 횟수입니다.

2.특징

1. 두 번째 해시 함수를 사용하여 주소 증분을 계산합니다.

2. 모든 위치는 최대 m-1회 감지 가능

4. 의사랜덤 시퀀스 방법

1.정의: di=의사랜덤 시퀀스

5.주의

1. 기존 요소를 임의로 삭제할 수는 없습니다. 동일한 해시 주소를 가진 다른 요소의 검색 주소가 잘리기 때문입니다.

2. 삭제 표시 및 논리적 삭제 표시 가능

3. 부작용: 여러 번 삭제하면 해시 테이블이 가득 찬 것처럼 보이지만 실제로는 사용하지 않는 위치가 여전히 많아 정기적인 유지 관리가 필요합니다.

2. 지퍼방식(링크방식)

1. 정의: 모든 동의어는 해시 주소로 고유하게 식별되는 선형 연결 목록에 저장됩니다.

2. 잦은 삽입과 삭제 상황에 적합하며 직접 물리적으로 삭제 가능

4. 해시 검색 및 성능 분석

1. 검색과정

0.초기화: Addr=Hash(키)

1. Addr에 기록이 있는지 확인하세요.

1. 기록 없음, 검색 실패

2. 기록이 있고 동일 검색이 성공적으로 실행될 때까지 기다립니다.

2. 주어진 충돌 처리 방법을 사용하여 "다음 해시 주소"를 계산하고 이 주소에 Addr을 설정한 후 1로 전송합니다.

2. 검색 효율성

1. 다음에 따라 다름: 해시 함수, 충돌 처리 방법, 로딩 인자

2. 채우기 요소(α): 테이블이 얼마나 가득 차 있는지 정의합니다.

α=테이블의 레코드 수 n/해시 테이블 길이 m

3. 평균 검색 길이는 α에 따라 달라지며 n 또는 m에 직접적으로 의존하지 않습니다.

질문 요약

1. 오류가 발생하기 쉬움

1. K개의 동의어는 선형 감지를 사용하여 해시 테이블에 채워지며, 이를 위해서는 K(K 1)/2번의 감지가 필요합니다.

1 2...K

2. 충돌 가능성은 로딩 요소의 크기에 비례합니다.

가득 차 있을수록 갈등이 발생할 가능성이 높아집니다.

3. 난수함수를 이용하여 해시함수를 구성할 수 없으며, 일반 검색도 수행할 수 없다.

2. 지식 포인트

1. 축적 원인

동의어 충돌에 대한 프로브 시퀀스와 비동의어에 대한 서로 다른 프로브 시퀀스가 얽혀 있습니다.

2. 평균 탐지 횟수 = 평균 검색 길이

3. 질문 유형

1.ASL 성공

검색 수 = 충돌 수 1

2.ASL 실패

해시 함수를 기반으로 필요한 전체 검색 위치를 결정하고, 비어 있지 않을 때까지 각 위치를 검색하고, 비어 있으면 해당 충돌 처리 방법을 사용하여 다시 검색해야 합니다.

5. 꼬치

1. 문자열의 정의

1. 공백 문자열: 빈 문자열이 아닌 하나 이상의 공백으로 구성됨

2. 선형 테이블은 단일 요소를 작업 개체로 사용하고 문자열은 하위 문자열을 작업 개체로 사용합니다.

2. 문자열 저장 구조

1. 고정 길이 순차 저장 표현

1. 선형 테이블 순차 스토리지와 유사하게 고정 길이 배열을 할당합니다.

2. 잘림: 미리 정의된 길이를 초과하는 문자열 값은 삭제됩니다.

2. 힙 할당 저장소 표현

1. malloc()과 free()를 사용하여 동적으로 할당하고 삭제합니다.

3. 블록체인 저장 표현

1. 선형 목록과 유사한 연결된 저장소, 각 노드는 하나 이상의 문자를 보유할 수 있습니다.

3. 문자열의 기본 연산

1. 연산의 최소 하위 집합(5): 다른 문자열 연산을 사용하여 구현할 수 없습니다.

1.문자열 할당: StrAssigh

2.문자열 비교: StrCompare

3. 문자열 연결: Concat

4. 문자열 길이 찾기: StrLength

5. 하위 문자열 찾기: SubString

4. 문자열 매칭 패턴

1.정의: 부분 문자열의 위치 지정 작업

2. 생각

1. 메인 문자열의 pos 문자부터 시작하여 패턴 문자열의 첫 번째 문자와 비교

2. 동일하면 계속해서 다음 문자를 하나씩 비교합니다.

3. 같지 않으면 기본 문자열의 다음 문자부터 비교를 다시 시작합니다.

3. 효율성

최악의 시간 복잡도: O(mn)

5. 향상된 패턴 매칭 알고리즘 - KMP 알고리즘

1. 문자열 접두사 및 부분 일치 값

1. 접두사: 마지막 문자를 제외한 모든 헤더 하위 문자열(첫 번째 위치에서만 시작할 수 있음)

2. 접미사: 첫 번째 문자를 제외한 모든 후행 하위 문자열(마지막 위치에서만 시작할 수 있음)

3. 부분 일치 값: 가장 긴 접두사와 접미사 길이가 동일함

2. 효율성

1. 시간 복잡도: O(m n)

3. 다음 배열 해결(수동)

1.다음 배열 값 = 가장 긴 접두사와 접미사 길이 1

2. 문자열 자체는 접두사 또는 접미사로 사용할 수 없습니다.

3. 일반적으로 next[1]=0(특정 질문에 따라 다름, -1인 경우 계산에 0을 사용하고 마지막으로 모든 숫자는 -1임)

4. next[i]의 i번째 요소가 일치하지 않는 경우 i번째 요소를 제외한 문자열 길이는 i-1입니다.

5. 문자열이 길면 처음 몇 개만 세어 답을 얻을 수 있습니다.

질문 요약

1.지식 포인트

1.KMP 알고리즘의 가장 큰 장점

기본 문자열은 역추적되지 않으며 i 포인터는 이동하지 않습니다. j=next[j]

2. 질문 유형

1. next[n]이 현재 해결되고 있다고 가정하고 next[]를 해결하는 빠른 방법, next[n-1]=m

0.기본값 다음[1]=0, 다음[2]=1

아래 첨자는 0부터 시작할 수도 있고, 숫자 값은 -1부터 시작할 수도 있습니다.

1. 문자열에는 n-1개의 문자가 있습니다. 처음 m개의 문자가 마지막 m개의 문자와 동일하면 next[n]=m 1, 3으로 이동합니다.

2. 처음 m개의 숫자가 마지막 m개의 숫자와 다를 때 m=1이면 다음[n]=1이면 3으로 이동합니다. 그렇지 않으면 m=m-1로 놓고 첫 번째 m-1과 마지막 m-1을 비교하여 동일하면 1로 가고 다르면 2로 계속합니다.

3. 작업 종료

2.KMP 매칭 프로세스

next[]의 값이 0부터 시작하면 아래 첨자 번호는 1부터 시작합니다. 일치하는 항목이 없으면 i 포인터는 이동하지 않습니다. j=next[j]

3. 오류가 발생하기 쉬움

1. 시험 중 next[] 값이 0부터 시작하는지 1부터 시작하는지 구별해야 합니다.

7장 정렬

1. 정렬의 기본 개념

1. 정렬의 정의

1. 알고리즘의 안정성은 알고리즘의 품질을 측정할 수 없습니다.

2. 내부 정렬: 모든 요소가 메모리에 배치됩니다.

3. 외부 정렬: 메모리와 외부 메모리 사이를 끊임없이 이동합니다.

질문 요약

1. 오류가 발생하기 쉬움

1. 시퀀스 리스트에 구현된 정렬 알고리즘이 연결 리스트에는 구현되지 않을 수 있습니다.

2. 동일한 선형 테이블을 정렬하기 위해 다른 정렬 방법을 사용하는 경우 얻은 정렬 결과가 다를 수 있습니다.

2.공식

1. n개의 키워드를 정렬하기 위한 최소 비교 횟수는 ┍log²(n!)┑입니다.

2. 삽입 정렬

1. 직접 삽입 정렬

1. 생각

1. 첫 번째 요소가 정렬되었다고 가정합니다.

2. 두 번째 요소부터 순서대로 이전 요소와 비교합니다. 즉시 교환이 만족되지 않으면 이미 정렬된 항목을 제자리에 정렬하고 뒤로 이동을 반복합니다.

2.특징

1. A[0]을 센티널로 복사하여 범위를 벗어난 첨자를 피하고 할당을 용이하게 하며 임시 변수를 적용할 필요성을 제거합니다.

2. 비교와 이동을 동시에

3.성능 분석

1. 시간 효율성

1. 최선의 경우: O(n)

매번 한 번만 비교하면 되며 이동할 필요가 없습니다.

2. 최악의 경우: O(n²)

2. 적용 가능성

시퀀스와 체인 모두 적합합니다. 대부분의 알고리즘은 시퀀스에만 적합합니다.

4. 알고리즘 구현

2. 중간 삽입 정렬

1. 생각

1. 먼저 요소를 삽입할 위치를 찾기 위해 반으로 접습니다.

2. 삽입할 위치 이후의 모든 요소를 균일하게 이동

2.특징

1. 비교 요소 수만 줄어들고 이동 횟수는 변경되지 않았습니다.

2. 비교 횟수는 초기 상태와 관련이 없으며 n개만 수행됩니다.

3.성능 분석

1. 시간 복잡도: O(n²)

이동 횟수(2단계 for 루프)에만 관련되며 비교 횟수와는 아무런 관련이 없습니다. 비교는 for 루프에서 완료된 작업일 뿐입니다.

2. 안정

4. 알고리즘 구현

3. Hill 정렬(증분 정렬 감소)

1. 생각

1. 먼저 단계 크기를 n/2로 취하여 여러 그룹으로 나누고 각 그룹에서 직접 삽입 정렬을 사용합니다.

2. 단계 크기를 절반으로 줄이고 단계 크기가 1이 될 때까지 계속합니다.

2.특징

1. 최적의 증분 시퀀스는 아직 발견되지 않았으며 시간 복잡도를 계산할 수 없습니다.

3.성능 분석

1. 시간 효율성

최악의 경우: O(n²)

2. 불안정

동일한 키워드가 서로 다른 하위 테이블로 분할될 수 있음

4. 알고리즘 구현

질문 요약

1. 오류가 발생하기 쉬움

1. 반삽입 정렬의 시간복잡도는 O(n²)

3. 교환정렬

1. 버블정렬

1. 생각

1. 마지막 요소부터 시작하여 인접한 두 요소를 역순으로 비교합니다.

2. 버블링 작업으로 인해 가장 작은 요소가 첫 번째 위치로 교체됩니다.

3. 다음 버블링 라운드에서는 이전 라운드에서 결정된 가장 작은 요소가 더 이상 참여하지 않으며, 정렬할 열은 한 요소만큼 감소됩니다.

4. 각 버블의 결과는 시퀀스의 가장 작은 요소가 최종 위치에 배치되고 n-1개까지 완성됩니다.

2.특징

1. 버블 정렬로 생성된 순서 있는 하위 시퀀스는 전역적으로 정렬되어야 하며 이는 직접 삽입 정렬과 다릅니다.

3.성능 분석

1. 시간 효율성

1. 최선의 경우: O(n)

버블링 후에도 플래그는 여전히 False이고 요소 교환이 없으며 루프가 직접 점프됩니다.

4. 알고리즘 구현

2. 퀵 정렬(분할 정복 방식)

1. 생각

1. 매번 현재 테이블의 첫 번째 요소를 기준 피벗(피벗 값)으로 사용하여 테이블을 나눕니다.

2.i는 첫 번째 요소(기본)를 가리키고, j는 마지막 요소를 가리킵니다.

3. j부터 시작하여 뒤에서 앞으로 기준선보다 작은 첫 번째 요소를 찾습니다. j는 이 요소의 위치를 가리키며, i가 가리키는 요소를 이 요소로 바꿉니다.

4. i부터 시작해서 앞에서 뒤로 기준선보다 큰 첫 번째 요소를 찾아 i가 이 요소의 위치를 가리키고, j가 가리키는 요소를 이 요소로 대체합니다.

5. j부터 다시 시작하여 i와 j 사이의 접촉이 멈출 때까지 반복합니다. 접촉 위치에 기준 값을 놓고 시퀀스를 두 부분으로 나눕니다. 앞 부분은 기준 값보다 작습니다. .

6. 두 하위 시퀀스의 첫 번째 요소를 기준 값으로 사용하고 작업을 반복합니다.

2.특징

1. 정렬된 하위 시퀀스는 생성되지 않지만 각 정렬 패스 후에 요소가 최종 위치에 배치됩니다.

2. 알고리즘의 순서가 높을수록 효율성은 낮아지고, 알고리즘이 무질서할수록 효율성은 높아집니다.

3.성능 분석

1. 공간 효율성

평균 경우: O(㏒₂n)

알고리즘은 재귀적이며 재귀 작업 스택이 필요하며, 그 크기는 재귀 트리의 깊이입니다.

최악의 경우: O(n)

2. 시간 효율성

1. 최악의 경우: O(n²)

순서는 기본적으로 순서 또는 역순입니다.

2. 최선의 경우(평균의 경우) : O(n㏒₂n)

4. 불안정

교환 키워드가 존재합니다

4. 효율성 향상 방법

1. 재귀적 분할로 얻은 하위 수열이 작을 경우 재귀적 분할은 더 이상 필요하지 않으며 후속 작업에는 직접 삽입 정렬이 사용됩니다.

2. 데이터를 나눌 수 있는 벤치마크를 선택해보세요.

1. 머리, 꼬리, 가운데 세 요소를 선택한 후 가운데 값을 취합니다.

2. 최악의 시나리오가 발생하지 않도록 벤치마크를 무작위로 선택

5. 알고리즘 구현

질문 요약

1. 오류가 발생하기 쉬움

1. 퀵정렬을 이용하여 숫자그룹을 정렬할 때 가장 빠른 상황

선택된 각 벤치마크는 테이블을 비슷한 길이의 두 개의 하위 테이블로 나눕니다.

2. 가능한 순서를 찾을 때 두 순서를 모두 고려해야 합니다(큰 것에서 작은 것, 작은 것에서 큰 것)

2. 지식 포인트

1. 퀵 정렬은 순차 저장에 가장 적합합니다.

3.알고리즘적 사고

1. 모든 홀수를 모든 짝수 앞으로 이동시키는 알고리즘 (최소 시간/공간)

1. 먼저 앞에서 뒤로 짝수 L(i)를 찾고, 뒤에서 앞으로 홀수 L(j)를 찾아 그 둘을 교환하고, i>j가 될 때까지 반복한다.

2. 퀵 정렬 기준, 1회 순회, 시간 O(n), 공간 O(1)

2. 네덜란드 국기 문제: 빨간색, 흰색, 파란색으로만 구성된 블록의 순서로 블록이 빨간색, 흰색, 파란색의 순서로 배열되고 시간은 O(n)입니다.

1. 순차적으로 스캔하여 빨간색을 앞쪽으로, 파란색을 뒤쪽으로 바꿉니다.

2. 세 개의 포인터, 하나의 작업 포인터, 하나는 머리를 가리키고, 하나는 꼬리를 가리키며, 스위치 문

참고: 양수, 음수, 0은 같은 방식으로 정렬됩니다.

3. 배열 L[1...n]에서 k번째로 작은 요소를 찾습니다.

0. k개 이상의 요소를 얻기 위해 직접 정렬을 사용할 수 있음 O(nlog2n) / 작은 상단 힙 사용 O(n klog2n)

1. 더 흥미진진한 퀵 정렬을 기반으로 하면 시간은 O(n)입니다.

2. 벤치마크를 선택하고 L[1...m-1]과 L[m 1...n]으로 나누어 퀵 정렬과 동일한 나눗셈 연산을 수행합니다. L(m)이 벤치마크입니다.

3. m과 k의 관계에 대해 토론하세요.

1.m=k, 벤치마크는 당신이 찾고 있는 요소입니다

2.m<k, 찾고 있는 요소가 후반부에 있습니다. 계속해서 후반부에서 k-m번째로 작은 요소를 재귀적으로 찾습니다.

3.m>k, 찾고 있는 요소가 전반부에 있습니다. 계속해서 전반부에서 k번째로 작은 요소를 재귀적으로 찾습니다.

4. n개의 숫자는 집합 A를 구성하며, 이는 두 개의 분리된 부분 집합 A1과 A2로 나뉩니다. 숫자는 n1과 n2이고 요소의 합은 s1과 s2입니다. 최소 |n1-n2| 및 최대 |s1-s2| 충족

1. 가장 작은 n/2개의 요소를 A1에 나머지는 A2에 넣고 퀵 정렬을 모방하여 분할한 후 기준 위치 i를 별도로 처리합니다.

2. i=n/2이면 그룹핑이 완료됩니다.

3. i<n/2인 경우 기본 요소와 이전 요소를 모두 A1에 넣고 i 이후의 요소를 계속 나눕니다.

4. i>n/2이면 기본 요소와 모든 후속 요소를 A2에 넣고 i 앞의 요소를 계속 나눕니다.

5. 모든 요소를 정렬할 필요가 없음, 평균 시간 O(n), 공간 O(1)

4.정렬을 선택하세요

1. 간단한 선택 정렬

1. 생각

1. 첫 번째 패스에서 가장 작은 요소를 찾아 이 요소를 첫 번째 요소와 교환합니다.

1. 두 번째 패스에서 가장 작은 요소를 찾아 이 요소를 두 번째 요소와 교환하고 n-1회 반복합니다.

2.특징

1. 각 정렬 단계는 요소의 최종 위치를 결정할 수 있습니다.

3.성능 분석

1. 시간 복잡도는 항상 O(n²)입니다.

요소 이동 횟수는 O(n)인 경우가 거의 없지만 비교 횟수는 초기 상태와 관련이 없으며 항상 n(n-1)/2입니다.

2. 불안정

가장 작은 요소를 찾은 후 직접 교환하면 원래 순서가 파괴됩니다.

4. 알고리즘 구현

2. 힙 정렬

1. 생각

1. 힙의 정의

큰 루트 힙(완전 이진 트리): 가장 큰 요소는 루트 노드이고, 루트가 아닌 노드의 값은 해당 부모 노드의 값보다 작거나 같습니다.

1.1 힙 작업

1. 힙의 최상위 요소를 삭제합니다.

먼저 마지막 요소를 힙의 최상위 요소와 교환합니다. 삭제한 후 힙의 최상위 요소를 아래쪽으로 조정하여 힙이 됩니다.

2. 삽입 작업

먼저 새 노드를 힙 끝에 배치한 다음 위쪽으로 힙을 조정합니다.

2. 초기 힙 구성(대형 루트 힙)

1. 두 번째 레이어의 마지막 노드부터 판단합니다.

2. 상위 노드가 아닌 노드의 하위 트리만 살펴봅니다. 하위 트리에 루트 노드보다 큰 노드가 있으면 더 큰 노드를 찾아서 루트 노드와 교환합니다.

3. 교환 후 다음 레벨 힙이 파괴되면 루트 노드까지 계속해서 위의 방법을 사용하여 다음 레벨 힙을 조정합니다.

3. 힙의 최상위 요소(최대값)를 출력하고, 마지막 요소를 힙의 최상위에 넣은 후, 힙의 상단을 아래쪽으로 조정하여 큰 상단 힙이 되도록 합니다.

4. 힙에 요소가 하나만 남을 때까지 작업을 반복합니다.

2.성능 분석

1. 시간복잡도는 항상 O(n㏒2n)이다

힙 구축 시간은 O(n)이고, 매번 O(h)마다 n-1 하향 조정이 있습니다.

2. 불안정

힙을 구축하면 원래 순서가 중단됩니다.

3. 공간 복잡도: O(1)

일정한 수의 보조 장치만 사용

3. 알고리즘 구현

선택 정렬이 불안정합니다.

질문 요약

1. 고전적인 질문

1. 각 요소에는 두 개의 데이터 항목 k1과 k2가 있습니다. 정렬: k1을 먼저 보고, k1이 동일한 값을 갖고, 그 다음 k2를 보고, 작은 값을 먼저 봅니다.

1. 먼저 정렬 순서를 결정합니다. K2가 먼저 정렬되고 k1이 먼저 정렬되어야 합니다.

2. k2 정렬에는 안정성 요구 사항이 없습니다. 효율성이 높은 알고리즘을 선택해 보세요.

3. k1을 정렬하려면 안정적인 알고리즘을 사용해야 합니다. 그렇지 않으면 정렬된 k2가 중단될 수 있습니다.

2. 질문 유형

1. 힙에 요소 삽입/삭제 시 비교 횟수

2. k번째(k≥5) 가장 작은 요소 이전에 부분 정렬된 시퀀스를 얻고 싶습니다.

1. 버블/단순선택/힙 정렬 가능

2. 처음 두 번은 kn입니다.

3. 힙 정렬, 구축할 초기 힙은 4n을 초과하지 않으며, k 요소를 얻는 데 걸리는 시간은 klog2n, 총 4n klog2n, k≥5일 때 최적입니다.

3. 데이터 시퀀스가 작은 루트 힙인지 확인

1. 두 가지 상황을 나누어야 합니다. 순서는 홀수와 짝수입니다.

2. 홀수인 경우: 단일 분기 노드가 없으면 상위 노드와 두 하위 노드를 직접 비교할 수 있습니다.

3. 짝수인 경우: 단일 분기 노드가 있으며 별도로 판단할 수 있으며 다른 노드는 정상입니다.

5. 병합 정렬과 기수 정렬

1. 병합 정렬

1. 생각

1. 먼저 길이가 1인 n개의 하위 테이블로 나누고 쌍으로 병합합니다.

2. 길이가 2인 하위 목록을 얻고 이를 다시 2개씩 병합하고 반복합니다.

2.성능 분석

1. 공간 복잡도: O(n)

병합된 데이터는 보조 배열에 복사되어야 하며 길이는 n입니다.

2. 시간복잡도 : O(n㏒2n)

각 병합은 O(n)이며 총 n번 수행됩니다. 분할된 하위 시퀀스는 초기 상태와 관련이 없습니다.

3. 알고리즘 구현

2. 기수 정렬

1. 생각

1. 최하위 우선(LSD)

1. 먼저 한 자리 숫자의 크기에 따라 시퀀스를 10개의 대기열(0~9, 위에서부터 아래로)에 넣습니다.

2. 첫 번째 대기열의 모든 요소를 10번째 대기열까지 순서대로 대기열에서 제거합니다.

3. 그런 다음 열의 자리에 따라 대기열에 들어가고 나가는 작업을 반복하고, 백 자리에 대해서도 동일한 작업이 수행됩니다.

4. 최상위 비트도 대기열에서 제거되면 순서대로입니다.

2. MSD(최상위 비트 우선)

1. 먼저 가장 높은 비트의 크기에 따라 시퀀스를 10개의 대기열(0~9, 위쪽 및 아래쪽 바깥쪽)에 넣습니다.

2. 번호가 1이 아닌 대기열을 재귀적으로 정렬하여 다음으로 높은 숫자의 크기에 따라 다시 10개의 대기열에 넣습니다.

3. 모든 큐에 숫자가 1개만 남을 때까지 재귀는 종료되며, 각 큐를 수집하고 이전 레이어로 돌아갑니다.

2.특징

1. 비교를 기반으로 하지 않고 다중 키워드 정렬 방식을 채택합니다.

3. 성능분석(LSD)

1. 공간 복잡도: O(r)

r은 숫자의 밑수입니다(기본 시스템은 무엇입니까).

2. 시간 복잡도: O(d(n r))

d번의 할당과 수집을 수행합니다. 하나의 할당은 O(n)이고 하나의 컬렉션은 O(r)입니다.

3. 안정

할당과 수집이 모두 순차적으로 수행됩니다.

질문 요약

1. 오류가 발생하기 쉬움

1. 10TB 데이터 파일을 정렬하려면 어떤 방법을 사용해야 합니까?

병합 정렬, 파일이 너무 큽니다. 내부 정렬을 사용할 수 없습니다. 외부 정렬만 사용할 수 있습니다. 일반적으로 병합 정렬을 사용합니다.

2. 지식 포인트

1. 각각 n개의 요소가 있는 두 개의 순서 목록을 하나의 순서 목록으로 병합합니다.

1. 최소 비교 횟수는 다음과 같습니다. n

2. 최대 비교 횟수는 2n-1입니다.

3. 질문 유형

1. 기수 정렬에서는 정렬 코드 비교가 몇 번 수행됩니까?

여러 할당 및 수집을 수행했습니다.

6. 다양한 내부 정렬 알고리즘의 비교 및 적용

1. 내부 정렬 알고리즘 비교

2. 내부 정렬 알고리즘 적용(요약)

1. 알고리즘 선택

1.n이 더 작습니다

1. 기록 자체가 작다

직접 삽입(비교 횟수 감소)/간단한 선택(교환 횟수 감소)

2. 기록 자체가 크다

간단한 선택

1.1 중간 규모(n<1000)

힐 정렬은 좋은 선택이다

2. n은 매우 크다(시간이 더 짧은 것을 선택)

1. 불안정하다

1. 퀵 정렬(Quick Sort): 무작위로 배포했을 때 평균 시간이 가장 짧은 최선의 방법

2. 힙 정렬: 퀵 정렬보다 보조 공간이 덜 필요합니다.

2. 안정

병합 정렬: 그러나 공간 복잡도가 가장 높습니다.

3.n은 매우 크고, 키워드 자릿수가 작아서 분해 가능

기수 정렬이 더 좋습니다

4. 순서는 기본적으로 순서대로 되어있습니다

직접 삽입 정렬(최고 효율성/최소 비교 횟수)/버블 정렬

가장 좋은 경우의 시간 복잡도는 O(n)입니다.

5.몇번의 정렬을 거친 결과

1. 한 번에 하나의 요소를 최종 위치에 배치합니다.

단순 선택/힙 정렬, 버블 정렬/퀵 정렬(교환)

빠른 정렬 요소만 가장 가치 있는 요소는 아니며, 나머지 3개는 모두 가장 가치 있는 요소입니다(첫 번째/마지막).

2. 처음 몇 가지 요소는 순서대로 있지만 최종 위치는 아닙니다.

직접 삽입

3. 마지막 여행이 시작되기 전에 모든 요소가 최종 위치에 있지 않을 수도 있습니다.

직접 삽입

4. 최종 위치에 요소가 있을 것이라는 보장은 없습니다.

직접 삽입/힐 정렬/병합 정렬

6. 가장 많은 것 중 몇 가지

1. 현재 평균 성능 측면에서 최고의 내부 정렬 알고리즘

빠른 정렬

2. 가장 많은 공간을 차지하는 알고리즘

병합 정렬 O(n)

Quicksort는 최악의 경우 O(n)입니다.

3. 기본적으로 순서대로 되었을 때 가장 빠른 것은 무엇인가요?

직접 삽입 정렬

4. 최선의 경우 선형 시간을 달성할 수 있습니다.

직접 삽입/버블 정렬

7.0 알고리즘 시간은 초기 시퀀스와 무관합니다.

선택 정렬(단순 선택/힙 정렬)/병합 정렬/기수 정렬

7.1 정렬 패스 수는 초기 순서와 관련이 없습니다.

직접 삽입/단순 선택은 모두 n-1회이고 기수 정렬은 d회에 고정됩니다.

7.2 이동 횟수는 초기 순서와 관련이 없습니다.

기수 정렬

기수 정렬은 초기 시퀀스와 관련이 없습니다.

8. 가장 효율적인 데이터 구조 찾기

힙(Heap): 주로 정렬용으로 설계되었으며 검색 시에는 순서가 지정되지 않습니다.

9. 순차적 스토리지를 체인 스토리지로 대체하면 시간 효율성이 떨어집니다.

Hill 정렬/힙 정렬(순차 테이블의 무작위 액세스 특성 활용)

2. 병합 정렬 개선

직접 삽입 정렬과 결합: 먼저 직접 삽입을 사용하여 더 긴 순서의 하위 시퀀스를 얻은 다음 쌍으로 병합하지만 여전히 안정적입니다.

3. 비교 기반 알고리즘

비교 결정 과정은 이진 트리로 설명할 수 있으므로 최소한 O(n㏒2n) 시간이 소요됩니다.

4. 기록 자체에는 많은 양의 정보가 포함되어 있습니다.

연결된 목록을 저장 구조로 사용하면 레코드 이동에 많은 시간을 소비하지 않아도 됩니다.

7.외부정렬

1. 외부정렬의 기본 개념

1. 외부 메모리 읽기 및 쓰기 횟수를 줄입니다.

병합 경로 수 늘리기/병합 세그먼트 수 줄이기

2. 병합 경로 수 증가(m)

패자나무

사용 후 비교 횟수는 m과 관련이 없습니다. m을 늘려 병합 트리의 높이를 줄일 수 있습니다.

3. 병합된 세그먼트 수를 줄입니다.

순열 선택 정렬

병합 세그먼트의 수를 줄이려면 병합 세그먼트의 길이를 늘립니다.

4. 길이가 다른 병합 세그먼트의 병합 순서 구성

최고의 병합 트리

m-ary 트리로 일반화된 허프만 트리

2. 외부 정렬 방법(병합 정렬)

1. 상대적으로 독립적인 두 단계

1. 병합된 세그먼트/직렬 문자열 가져오기

n개의 레코드는 메모리 버퍼의 크기에 따라 여러 개의 레코드로 나누어 순차적으로 메모리에 읽어 들여 내부 정렬 방식으로 정렬한 후 외부 메모리에 다시 쓴다.

2. 병합된 세그먼트를 하나씩 병합하여 완료될 때까지 병합된 세그먼트가 작은 것에서 큰 것으로 증가하도록 합니다.

2. 병합 패스 수 S = 트리 높이 = ┌㏒mⁿ┐

n - 초기 병합 세그먼트 수 m - 병합 경로 수 ┌┐ - 반올림

3. 다중 방향 균형 병합 및 패자 트리

1. m이 증가함에 따라 내부 병합 시간이 증가합니다.

1. m 증가로 인한 외부 메모리 액세스 횟수 감소로 인한 이점을 상쇄합니다.

2. 일반적인 내부 병합 정렬은 사용할 수 없습니다.

2. 패자 트리(완전 이진 트리)

1. 리프 노드

현재 비교에 참여하고 있는 레코드

2. 내부 노드

왼쪽과 오른쪽 하위 트리에 패자의 시퀀스 번호를 기억하고 루트 노드까지 승자가 위쪽으로 계속 비교하도록 합니다.

3. 루트 노드

값 자체가 아닌 현재 최소/최대 숫자의 일련번호(승자)

3. 패자 트리를 이용하여 최소값 순번을 구한 후, 최소값 시퀀스 번호를 꺼내고 그 위치에 다음 키워드를 추가한 후 비교를 계속하여 패자 트리를 구성한다.

4. 패자 트리를 사용한 후에는 비교 횟수가 m과 관련이 없습니다. m을 늘려 병합 트리의 높이를 줄일 수 있습니다.

5.m는 그다지 크지 않을수록 좋습니다

m이 증가할수록 입력 버퍼는 증가하고, 용량은 감소하며, 내부 메모리와 외부 메모리 사이의 데이터 교환 횟수가 증가합니다.

4. 교체 선택 정렬(가장 긴 초기 병합 세그먼트 생성)

1. 생각

1. 먼저 작업 영역에서 가장 작은 숫자 a를 선택합니다.

2. 그런 다음 a보다 큰 숫자 중 가장 작은 숫자를 가져와 이 병합 섹션에 넣고, a보다 작은 숫자를 다음 병합 섹션에 넣습니다.

5. 최고의 병합 트리

1. 정의(일반화된 m-ary 허프만 트리)

1. 리프 노드

병합에 참여하는 초기 병합 세그먼트

2. 리프 노드의 가중치

초기 병합 세그먼트의 레코드 수

3. 리프 노드에서 루트 노드까지의 경로 길이

병합 패스 수

4.비리프 노드

병합으로 생성된 새로운 병합 세그먼트

5. 병합 트리의 가중 경로 길이

총 읽기 레코드 수

모든 리프 노드가 통과한 간선 수 * 가중치

2. 생각

더 적은 수의 레코드가 있는 병합 세그먼트를 먼저 병합하고 더 많은 레코드가 있는 병합 세그먼트를 마지막에 병합하도록 합니다.

3. 최적의 병합 트리는 엄격한 m-ary 트리입니다.

1. 마지막 누락 항목이 엄격한 m-ary 트리를 형성하기에 충분하지 않은 경우 길이가 0인 "가상 세그먼트"를 추가하고 먼저 병합합니다.

2. 빈 병합 세그먼트 수 = m-u-1

당신=(n0-1)%(m-1)

n0 - 차수가 0인 노드 수(초기 병합 세그먼트 수) m-m 트리

질문 요약

1. 질문 유형

1. 총 n개의 레코드가 있고, 작업공간은 하나의 레코드를 수용할 수 있으며, m-way 균형 병합이 수행됩니다.

1. 초기 병합 세그먼트 수 r=n/a, 병합 패스 수 s=┌㏒m(r)┐

2.5개의 초기 병합 세그먼트(각각 20개의 레코드 포함, 5방향 균형 병합 사용) 패자 트리가 없는 경우와 패자 트리가 있는 경우의 비교 수

1. 패자 트리를 사용하지 않습니다. 가장 작은 레코드를 선택하려면 5개의 레코드를 4번 비교해야 합니다. 가장 작은 레코드를 선택하려면 총 99개의 작업이 필요합니다(4*99=396).

2. 패자 트리 사용: 패자 트리의 높이는 h=3이며, 매번 가장 작은 것을 선택하고, 비교 횟수는 h를 초과하지 않으며, 총 100회, 최대 300회

3. m-way 균형 병합, 입력 및 출력 버퍼 수 수행

1. 정상 상황(직렬 작동): m개의 입력 버퍼와 1개의 출력 버퍼가 필요합니다.

2. 입출력 병렬 작동: 2m 입력 버퍼, 2개의 출력 버퍼

4. 동시에 사용 가능한 입출력 파일의 총 개수는 15개를 초과할 수 없습니다.

최대 14가지 병합 방법 가능