빠른 정렬은 토니 홀에 의해 개발된 정렬 알고리즘이다. 평균 상태에서는 정렬 n 개 항목에 대한 nlogn 비교가 필요하다. 최악의 상태에서는 nlogn 비교가 필요하지만, 이러한 상황은 흔하지 않다. 사실, 빠른 정렬은 다른 nlogn 알고리즘보다 일반적으로 훨씬 빠르다. 왜냐하면 그것의 내부 루프 (inner loop) 이 대부분의 구조에서 매우 효율적으로 구현될 수 있기 때문이다.
급속한 정렬: 분할 및 정복 (Divideandconquer) 전략을 사용하여 하나의 리스트를 두 개의 하위 목록으로 나누는 방법.
알고리즘 단계:
1, 숫자의 열에서 하나의 요소를 선택합니다.
2, 재조정 수열, 기준값보다 작은 모든 요소를 기준값 앞에 놓고, 기준값보다 큰 모든 요소를 기준값 뒤에 놓는다. 이 분할이 빠져나간 후, 기준값은 수열의 중간 위치에 있다. 이것을 분할 (partition) 동작이라고 한다.
3, 회귀적으로 (recursive) 기준값 요소보다 작은 소수열과 기준값 요소보다 큰 소수열을 정렬한다.
회귀의 가장 기본적인 경우, 수열의 크기가 0 또는 1이므로 항상 정렬되어 있습니다. 회귀가 계속되고 있지만, 이 알고리즘은 항상 탈퇴합니다. 왜냐하면 반복 (iteration) 에 따라 적어도 하나의 요소를 마지막 위치로 옮기기 때문입니다.
무더기 정렬 (Heapsort) 은 무더기와 같은 데이터 구조를 활용하여 설계된 정렬 알고리즘을 의미한다. 무더기는 거의 완전한 이차 나무의 구조이며 동시에 무더기의 특성을 충족시킨다. 즉, 자각의 키값 또는 인덱스는 항상 그 부모 노드보다 작거나 크다.
알고리즘 단계:
1, H [0...n-1] 를 생성합니다
2, 모음 앞 (最大) 과 모음 뒷을 교환합니다
3, 1으로 줄이고 shift_down ((0) 을 호출하여 새로운 대수열의 꼭대기 데이터를 그 위치에 조정합니다.
4번, 2번을 반복해서
합렬 (Mergesort, 타이완어 번역: 합렬) 은 합렬에 기반한 효과적인 분류 알고리즘이다. 이 알고리즘은 분할 및 정복을 사용하는 매우 전형적인 응용 프로그램이다.
알고리즘 단계:
1, 두 개의 정렬된 시퀀스의 합으로 된 크기의 공간을 신청합니다.
2, 두 개의 포인터를 두 개의 정렬된 시퀀스의 시작 위치로 설정합니다.
3, 두 지표가 가리키는 요소를 비교하고, 상대적으로 작은 요소를 선택하여 합동 공간에 넣고, 지표를 다음 위치로 이동합니다.
4 단계 3을 반복합니다.
5, 다른 일련의 나머지 모든 요소를 직접 합동 일련의 끝으로 복사합니다.
이분점 검색 알고리즘은 정렬된 배열에서 특정 요소를 찾는 검색 알고리즘이다. 검색 프로세스는 배열의 중간 요소에서 시작되며 중간 요소가 바로 찾고자 하는 요소라면 검색 프로세스가 종료된다. 특정 요소가 중간 요소보다 크거나 작은 경우, 배열의 중간 요소보다 크거나 작은 절반에서 검색하고, 처음부터 같은 중간 요소로부터 비교한다. 만약 단계적 배열이 비어있다면, 표시를 찾을 수 없다. 이 검색 알고리즘은 비교할 때마다 검색 범위를 한 번 축소한다.
BFPRT 알고리즘은 어떤 n개 요소의 연속에서 k대 (k소) 요소를 선택하는 고전적인 문제를 해결하는데, 기교한 분석을 통해 BFPRT는 최악의 경우에도 선형 시간 복잡성을 유지할 수 있도록 보장한다. 이 알고리즘의 생각은 빠른 순서 생각과 유사하다. 물론, 알고리즘이 최악의 경우에도 o (n) 시간 복잡성을 유지할 수 있도록 다섯 명의 저자가 세련한 처리를 했다.
알고리즘 단계:
1, n개 요소를 5개 그룹으로 나누고 n/5 (위쪽 경계) 그룹으로 나누는 것이다.
2, 각 집합의 중심을 제거하고, 어떤 분류 방법을 사용하든, 예를 들어, 분류를 삽입한다.
3, 역습적인 호출 선택 알고리즘은 이전 단계의 모든 중위들의 중심을 찾는데, x로 설정되어 있고, 짝수 중위들의 경우 중간에 작은 것을 선택하도록 설정되어 있다.
4, x를 사용하여 배열을 나누면 x보다 작은 개수는 k이고 x보다 큰 개수는 n-k이다.
5, i==k 경우 x를 반환한다; i
종료 조건: n=1이 되면 i 소수 요소가 반환된다.
깊은 우선 순위 검색 알고리즘 (Depth-First-Search) 은 나무의 깊이를 따라 나무의 노트를 탐색하고, 가능한 한 깊은 검색 나무의 지점을 탐색하는 검색 알고리즘이다. 노트 v의 모든 변이 탐색되었을 때, 검색은 발견된 노트 v의 쪽의 시작 노트로 되돌아간다. 이 과정은 이미 발견된 모든 노트에서 접근할 수 있는 모든 노트까지 계속된다. 아직 발견된 노트가 없다면, 그 중 하나를 원본 노트로 선택하고 모든 노트들이 방문될 때까지 이 과정을 반복한다. DFS는 블라인드 검색에 속한다.
심도 우선 순위 검색은 그래프 이론에서 고전적인 알고리즘으로, 심도 우선 순위 검색 알고리즘을 이용하여 목표 그래프에 해당하는 도포 정렬 목록을 생성할 수 있다. 도포 정렬 목록을 사용하여 최대 경로 문제와 같은 많은 관련 그래프 문제들을 쉽게 해결할 수 있다. 일반적으로 쌓음 데이터 구조를 사용하여 DFS 알고리즘을 구현하는 데 도움을 준다.
이 글은 한 가지 중요한 부분입니다.
1, 꼭대기 v에 접근;
2, v의 접근되지 않은 인접 연결점으로부터 순차적으로 그래프의 깊이 우선 순위를 탐색한다. 그래프와 v의 경로가 만나는 꼭대기까지 접근한다.
3, 이 때 도표에 아직 접근되지 않은 꼭대기가 있다면, 접근되지 않은 꼭대기에서 시작하여 도표의 모든 꼭대기가 접근될 때까지 다시 깊이 우선 순위를 탐색한다.
위 설명은 좀 더 추상적일 수 있습니다. 예를 들어:
DFS는 접근 그래프의 한 꼭대기 v에서 시작하여, v에서 출발하여, 그 인접한 꼭대기 w1의 어느 하나에 접근한다; 다시 w1에서 출발하여, w1과 인접하지만 아직 접근되지 않은 꼭대기 w2에 접근한다; 그리고 다시 w2에서 출발하여, 유사한 접근을 한다,... 이렇게 계속하여, 모든 인접한 꼭대기들이 방문된 꼭대기 u에 도달할 때까지.
다음으로, 한 단계 물러서서, 방금 방문한 정상으로 돌아가서, 방문되지 않은 다른 인접한 정상이 있는지 확인합니다. 만약 그렇다면, 이 정상을 방문하고, 그 후 이 정상에서 출발하여, 이전과 유사한 방문을 수행합니다. 만약 그렇지 않다면, 다시 한 단계 물러서서 검색합니다. 연결 지도의 모든 정상이 방문될 때까지 위의 과정을 반복합니다.
너비 우선 검색 알고리즘 (Breadth-First-Search) 은 그래픽 검색 알고리즘이다. 간단히 말해서, BFS는 루트 노트에서 시작하여 나무의 너비에 따라 나무의 노트들을 가로지르는 것이다. 모든 노트들이 접속되면 알고리즘은 중단된다. BFS는 또한 맹목적인 검색이다. 일반적인 쿼리 데이터 구조를 사용하여 BFS 알고리즘을 구현하는 데 도움을 준다.
알고리즘 단계:
1, 먼저 루트 노트를 줄에 넣습니다.
2, 행렬에서 첫 번째 노트를 뽑고 목표인지 확인합니다.
만약 목표가 발견되면 검색을 종료하고 결과를 다시 전송합니다. 다른 경우, 확인되지 않은 모든 직접 하위 노트를 큐에 추가합니다.
3, 쿼리가 비어있는 경우, 전체 그래프가
4 단계 2을 반복합니다.
디크스트라 알고리즘 (Dijkstra salgorithm) 은 네덜란드의 컴퓨터 과학자 에즈헬 디크스트라에 의해 제안되었다. 디크스트라 전용 알고리즘은 비부정적 권한의 방향 그래프의 단일 소스 최단 경로 문제를 해결하는 광범위한 우선 순위 검색을 사용하여 최단 경로 트리를 얻습니다. 이 알고리즘은 종종 경로 알고리즘 또는 다른 그래프 알고리즘의 하위 모듈로 사용됩니다.
이 알고리즘의 입력에는 가중된 가중된 도표 G와 G의 소스 꼭짓점 S가 포함되어 있습니다. 우리는 V로 G의 모든 꼭짓점들의 집합을 나타냅니다. 그래프의 각 변은 두 꼭짓점들이 형성된 정렬된 요소 쌍입니다. ((u,v) 는 꼭짓점 u에서 v로 연결된 경로가 있음을 나타냅니다. 우리는 E로 G의 모든 변의 집합을 나타냅니다. 변의 무게는 가중 함수 w:E→[0,∞]에 의해 정의됩니다.
따라서 w (u,v) 는 꼭대기 u에서 꼭대기 v까지의 비비중 (weight) 이다. 측면의 무게는 두 꼭대기 사이의 거리로 생각할 수 있다. 두 점 사이의 경로의 무게는 그 경로의 모든 측면의 무게의 합이다. V에 꼭대기 s와 t가 있는 것으로 알려져 있으며, 디지스트라 알고리즘은 s에서 t까지의 최소 무게 경로를 찾을 수 있다. 예를 들어, 가장 짧은 경로). 이 알고리즘은 또한 한 그래프에서 한 꼭대기 s에서 다른 모든 꼭대기까지의 가장 짧은 경로를 찾을 수 있다. 비비중 (negative power) 을 포함하지 않는 방향 그래프에 대해서는 디지스트라 알고리즘은 현재 알려진 가장 빠른 단일 소스 최단 경로 알고리즘이다.
알고리즘 단계:
1, 초기 시정 S={V0}, T={ 나머지 꼭대기}, T 중 꼭대기 대응 거리의 값
만약
2, T에서 가장 작은 거리가 있는 꼭대기 W를 선택하고 S에 있지 않은 것을 선택하고 S에 추가합니다
3, 나머지 T 중점의 거리의 값을 수정한다: W를 중점으로 추가하여 V0에서 Vi의 거리의 값을 축소하면 이 거리의 값을 수정한다.
위 단계 2와 3를 반복해서 S에 모든 꼭대기가 있는 W=Vi까지 반복합니다.
동적 프로그래밍 (Dynamic programming) 은 수학, 컴퓨터 과학 및 경제학에서 원 문제를 비교적 간단한 하위 문제로 분해하는 방식으로 복잡한 문제를 해결하는 방법이다. 동적 프로그래밍은 종종 중복 하위 문제와 최우수 하위 구조의 특성을 가진 문제에 적용되며, 동적 프로그래밍 방법은 단순 해법보다 훨씬 더 짧은 시간이 소요된다.
동적 계획의 기본 아이디어는 매우 간단하다. 일반적으로 주어진 문제를 해결하기 위해 우리는 그 문제를 해결하기 위해 그 문제를 풀기 위해 여러 부분을 풀어야 한다. 즉, 소수 문제, 소수 문제를 다시 합쳐서 원 문제를 해결한다. 일반적으로 많은 소수 문제들이 매우 유사하기 때문에 동적 계획법은 각 소수 문제를 한 번만 해결하려고 시도하여 계산량을 줄여줍니다. 주어진 소수 문제를 풀었을 때, 그것을 기억 저장하여 다음 번 같은 소수 문제를 해결해야 할 때 직접 확인합니다. 이 방법은 반복 소수 문제들의 수가 입력 크기에 대한 지수적으로 증가할 때 특히 유용합니다.
이 모든 것이 다이나믹 계획에 대한 가장 고전적인 문제입니다.
알고리즘 단계:
1, 최우수 구조적 특성. 문제의 최우수 해결책에 포함된 소문제의 해결책이 또한 최우수인 경우, 우리는 그 문제를 최우수 구조적 특성 (즉 최우수 최적화 원리를 충족시키는) 이라고 한다. 최우수 구조적 특성 (최우수 구조적 특성) 은 동적 계획 알고리즘에 문제를 해결하는 데 중요한 단서를 제공한다.
2, 소문제 중복성. 소문제 중복성 (subproblem overlap) 은 소문제를 상위에서 아래로 계산하는 경우, 생성되는 소문제가 항상 새로운 문제가 아니며, 일부 소문제가 여러 번 반복적으로 계산되는 것을 의미합니다. 동적 계획 알고리즘은 이러한 소문제 중복성을 활용하여 각 소문제에 대해 한 번만 계산하고 그 계산 결과를 테이블에 저장하고, 다시 계산이 필요한 소문제를 계산할 때, 단순히 테이블에서 결과를 살펴보고 더 높은 효율성을 얻을 수 있습니다.
순수 베이어스 분류 알고리즘은 베이어스 정리에 기초한 간단한 확률 분류 알고리즘이다. 베이어스 분류의 기초는 확률 추론, 즉 다양한 조건의 존재가 불확실하고 그 확률이 발생했을 때만 추론과 의사결정 작업을 수행하는 방법이다. 확률 추론은 확실성 추론에 대응한다. 순수 베이어스 분류는 샘플의 각 특성이 다른 특성과 관련이 없다고 가정하는 독립 가정에 기초한다.
순수 베이어스 분류기는 정확한 자연 확률 모델에 의존하고 있으며, 감독된 학습이 있는 샘플 세트에서 매우 좋은 분류 효과를 얻을 수 있다. 많은 실제 응용분야에서 순수 베이어스 모델의 매개 변수 추정은 최대 유사성 추정 방법을 사용한다. 즉, 순수 베이어스 모델은 베이어스 확률이나 어떤 베이어스 모델도 사용하지 않고 작동한다.
이러한 순수한 생각과 지나치게 단순화된 가정에도 불구하고, 순수한 베이스 분류기는 많은 복잡한 현실 상황에서도 상당히 좋은 효과를 낼 수 있다.