프로그래머가 알아야 할 10가지 기본 실용 알고리즘과 이에 대한 설명

• ### 알고리즘 1: 빠른 서열 알고리즘

빠른 정렬은 토니 홀이 개발한 정렬 알고리즘이다. 평균 상황에서 n개의 항목을 정렬하기 위해서는 nlogn (nlogn) 가 필요하며, 최악의 경우에는 nlogn (nlogn) 가 필요하지만, 이러한 상황은 흔하지 않다. 사실, 빠른 정렬은 일반적으로 다른 nlogn (nlogn) 알고리즘보다 훨씬 빠르다. 왜냐하면 그것의 내부 순환 (innerloop) 은 대부분의 구조에서 매우 효율적으로 구현될 수 있기 때문이다.

빠른 정렬은 분할법 (Divideandconquer) 을 사용하여 연속적인 리스트를 두 개의 서브 리스트로 나눈다.

알고리즘 단계:

• 1은, 행렬에서 하나의 요소를 선택하여, 基准 ((pivot)) 이라고 합니다.

• 2 , 재배열 수열, 기준값보다 작은 모든 요소는 기준값의 앞에 배치하고, 기준값보다 큰 모든 요소는 기준값의 뒤에 배치한다. 동일한 숫자는 어느 쪽으로도 갈 수 있다. 이 분할이 종료된 후, 이 기준은 수열의 중간 위치에 있다. 이것은 분할 (partition) 작업이라고 한다.

• 3 , 회귀적으로 ((recursive) 기준값 요소보다 작은 하위수열과 기준값 요소보다 큰 하위수열을 정렬한다.

  회귀의 가장 기본적인 상황은, 수의 크기가 0 또는 1 이므로, 즉 영원히 모두 잘 정렬되어 있다. 계속 회귀하더라도, 이 알고리즘은 항상 탈퇴한다. 왜냐하면, 각 iteration에서, 적어도 하나의 요소를 그것의 마지막 위치에 놓는다.

• ### 알고리즘 2: 서열 알고리즘

Heapsort () 은 heapsort의 데이터 구조를 이용하여 설계된 정렬 알고리즘을 의미한다. heapsort은 거의 완전한 이차나무 구조이며, 동시에 heapsort의 성질을 만족시킨다. 즉, 하위 노드의 키값 또는 인덱스는 항상 그 부모 노드보다 작거나 크다.

집합 정렬의 평균 시간 복잡도는 O ((nlogn) 。

알고리즘 단계:

• 1 H더미를 생성합니다.[0..n-1]

• 2, 스택 헤더 (최대값) 와 스택 테드 (최대값) 를 교환합니다.

• 3, 더 작은 1로 더 많은 데이터의 크기를 축소하고, shift_down () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () ()

• 4.. 2번을 반복해서 1번의 크기를 얻습니다.

• 알고리즘 3: 종합 순서

병합순렬 (Mergesort, 타이완어 번역: 합병순렬) 은 병합작업을 기반으로 한 효과적인 순서 알고리즘이다. 이 알고리즘은 분배법 (DivideandConquer) 을 사용하는 매우 전형적인 응용이다.

알고리즘 단계:

• 1, 요청 공간, 두 개의 정렬된 시퀀스의 합산된 시퀀스를 저장하기 위한 공간

• 2 , 두 개의 지점을 설정 하 고, 초기 위치 각각 두 개의 이미 정렬 된 일련의 시작 위치

• 3, 두 지점의 요소를 비교하고, 비교적 작은 요소를 선택하여 결합 공간에 넣고, 지점을 다음 위치로 이동합니다.

• 4 단계 3을 반복합니다.

• 1. 다른 서열의 나머지 모든 요소를 통합 서열의 끝에 직접 복사합니다.

• 알고리즘 4: 2차 검색 알고리즘

이분수 검색 알고리즘 (二分查找算法, 영어: binary search algorithm) 은 순서로 배열된 배열에서 특정 요소를 찾는 검색 알고리즘이다. 검색 과정은 배열의 중간 요소에서 시작하여, 중간 요소가 바로 찾고자 하는 요소라면 검색 과정은 종료된다. 특정 요소가 중간 요소보다 크거나 작다면 배열의 중간 요소보다 크거나 작은 절반에서 검색하고, 시작과 같은 중간 요소에서 비교를 시작한다. 어떤 단계에 계수수가 비어 있다면, 대상이 찾을 수 없다. 이러한 검색 알고리즘은 매번 비교할 때마다 검색 범위를 반으로 줄여준다. 반복 검색은 매번 검색 영역을 반으로 줄여서 복잡도 시간을 ((Οlogn)) 로 줄인다.

• ### 알고리즘 5: BFPRT (선형 검색 알고리즘)

BFPRT 알고리즘이 해결하는 문제는 매우 고전적이어서, 어떤 n개의 요소의 연속에서 k번째 큰 (k번째 작은) 요소를 선택하여, 재치 있는 분석을 통해 BFPRT는 최악의 경우에도 여전히 선형적 시간 복잡성을 보장할 수 있다. 이 알고리즘의 생각은 빠른 순서 아이디어와 유사하며, 물론, 최악의 경우에도 알고리즘이 여전히 o (n) 의 시간 복잡성을 달성할 수 있도록, 다섯 명의 알고리즘 작가는 정교한 처리를 했다.

알고리즘 단계:

• 1, n개 요소를 5개씩 1개로 나누고, n/5 (최고 경계) 그룹으로 나누십시오.

• 2, 각 그룹의 중위치를 다, 임의의 정렬 방법, 예를 들어 삽입 정렬.

• 3, 회귀 호출 선택 알고리즘은 이전 단계의 모든 중위자의 중위자를 찾아, x로 설정하고,偶数 중위자의 경우 중소 중 하나를 선택하도록 설정한다.

• 4 , x를 사용하여 배열을 나누기 위해, x보다 작은 숫자는 k이고, x보다 큰 숫자는 n-k이다.

• 5 , 만약 i==k이라면, x를 반환한다; 만약 ik라면, x보다 큰 원소들 중 i-k보다 작은 원소들을 찾아내기 위해 반복한다.

  종료 조건: n=1일 때, 반환되는 것은 i 소원소이다.

• 알고리즘 6: DFS (Deep Priority Search)

깊이-첫-검색 (영어: depth-first-search) 은 검색 알고리즘의 한 종류이다. 나무의 깊이를 따라 나무의 노드를 돌아다니며, 가능한 한 깊은 검색 나무의 분파를 찾는다. 노드 v의 모든 변이 탐색되었을 때, 검색은 발견된 노드 v의 변의 시작 노드로 돌아간다. 이 과정은 발견된 소스 노드에서 도달할 수 있는 모든 노드까지 계속된다. 아직 발견되지 않은 노드가 존재한다면, 그 중 하나를 소스 노드로 선택하고 위의 과정을 반복한다. 전체 프로세스는 모든 노드가 방문될 때까지 반복된다.

깊이 우선 검색은 도형학에서 고전적인 알고리즘으로, 깊이 우선 검색 알고리즘을 사용하여 목표 도형의 대응 토플 서열표를 생성할 수 있으며, 토플 서열표를 사용하여 최대 경로 문제 등과 같은 많은 관련 도형 문제를 편리하게 해결할 수 있다. 일반적으로 더미 데이터 구조를 사용하여 DFS 알고리즘을 구현하기 위해 보조한다.

이 그래프의 단계들을 깊이 살펴보면

• 1위, 정상에 도달 v;

• 2., 순차적으로 v의 방문되지 않은 인접한 연결점으로부터 시작하여, 도표의 깊이 우선 순위를 이동합니다. 도표와 v의 경로가 일치하는 꼭대기까지 모두 방문됩니다.

• 1. 만약 이 시간표의 꼭대기가 아직 방문되지 않은 경우, 방문되지 않은 꼭대기에서 시작하여, 모든 꼭대기가 방문될 때까지 다시 깊이 우선 순위를 이동한다.

  위와 같은 설명은 추상적일 수 있습니다. 예를 들어:

  DFS는 접근 도표에서 어떤 하나의 초점 v를 시작한 후, v에서 출발하여, 그것의 모든 인접한 초점 w1을 방문한다; 다음으로 w1에서 출발하여, w1과 인접한 그러나 아직 방문하지 않은 초점 w2를 방문한다; 그리고 다시 w2에서 출발하여, 비슷한 방문을 한다… 이렇게 계속하다, 모든 인접한 초점들이 방문된 초점 u까지다.

  다음으로, 한 걸음 뒤로 물러나서, 방금 방문한 꼭대기로 돌아가서, 방문되지 않은 다른 인접한 꼭대기가 있는지 확인한다. 있다면, 이 꼭대기를 방문하고, 그 다음에 이 꼭대기에서 출발하여, 앞서 언급한 것과 유사한 방문을 한다. 그렇지 않다면, 한 걸음 뒤로 물러나서 검색한다. 연결 지도의 모든 꼭대기가 방문될 때까지 위의 과정을 반복한다.

• 알고리즘 7: BFS (Broad Foresight Prioritized Search)

폭 우선 검색 알고리즘 (Broadth-First-Search) 은 그래픽 검색 알고리즘이다. 간단히 말해서, BFS는 루트 노트에서 시작하여 나무의 폭을 따라 나무의 노트를 횡단한다. 모든 노트가 접근되면 알고리즘은 중단된다. BFS는 또한 맹목적인 검색이다. 일반적으로 배열 데이터 구조를 사용하여 BFS 알고리즘을 보조한다.

알고리즘 단계:

• 1, 먼저 루트 노드를 큐에 넣습니다.

• 1. 큐에서 첫 번째 노드를 꺼내서 목표인지 확인한다.

  목표물을 발견하면 검색을 종료하고 결과를 전달한다. 아니면 아직 검사되지 않은 모든 직접 하위 노드를 큐에 추가합니다.

• 3 , 줄이 비어 있다면, 전체 지도가 을 검사했음을 의미하며, 에서 찾고자 하는 목표가 없다는 것을 의미한다. 검색을 종료하고 회귀 은 목표 을 찾지 못했다.

• 4단계 2을 반복하세요.

• 알고리즘 8: Dijkstra 알고리즘

디크스트라 알고리즘은 네덜란드의 컴퓨터 과학자 이즈헤르 디크스트라가 제안한 것이다. 디코스처 알고리즘은 광대 우선 검색을 사용하여 비负权定向图의 단일 소스 최단 경로 문제를 해결하고, 알고리즘은 최종적으로 최단 경로 나무를 얻는다. 이 알고리즘은 종종 경로 알고리즘 또는 다른 도표 알고리즘의 하위 모듈로 사용됩니다.

이 알고리즘의 입력에는 가중된 방향 도표 G, 그리고 G의 원천 꼭대기 S가 포함되어 있다. 우리는 V로 G의 모든 꼭대기들의 집합을 나타낸다. 각 도표의 변들은 두 꼭대기들이 형성한 정렬 요소 쌍이다. u,v는 꼭대기 u에서 v까지의 경로가 연결되어 있다. 우리는 E로 G의 모든 변들의 집합을 나타내고, 변들의 무게는 가중 함수 w:E→[0,∞] 정의

따라서, w(u,v) 는 꼭대기 u에서 꼭대기 v까지의 비하급수 ((weight) 이다. 측면의 무게는 두 꼭대기 사이의 거리로 상상할 수 있다. 두 지점 사이의 경로의 무게는 그 경로에 있는 모든 측면의 무게의 총합이다. V에는 꼭대기 s와 t가 있는 것으로 알려져 있으며, Dijkstra 알고리즘은 s에서 t까지의 최소 무게 경로를 찾을 수 있다.

알고리즘 단계:

• 1 , 초기 시점 S = {V0}, T = { 나머지 꼭대기}, T 중 꼭대기 대응 거리 값 만약 ,d(V0,Vi) 가 존재한다면 에 대한 가중치 만약 가 존재하지 않는다면, d (V0,Vi) 는∞이다.

• 2, T에서 가장 작은 거리가 되는 꼭대기 W를 선택하고 S에 포함하지 않고 S에 추가합니다.

• 3, 나머지 T의 꼭대기점의 거리값을 수정한다: 중간 꼭대기점으로 W를 추가하면, V0에서 Vi의 거리값을 줄여서, 이 거리값을 수정한다

  위 단계 2와 3를 반복하여 모든 꼭대기를 S에 포함할 때까지, 즉 W=Vi까지

• 알고리즘 9: 동적 계획 알고리즘

다이내믹 프로그래밍 (Dynamicprogramming) 은 수학, 컴퓨터 과학, 경제학에서 사용되는데, 원문 문제를 비교적 간단한 하위문제로 분해하여 복잡한 문제를 해결하는 방법이다. 다이내믹 프로그래밍은 종종 중첩 하위문제와 최우선 구조의 특성을 가진 문제에 적용되며, 다이내믹 프로그래밍 방법은 단순 해법보다 훨씬 적은 시간을 소비한다.

다이내믹 플래닝의 기본 아이디어는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서는 그것의 여러 부분을 풀어야 한다. 그리고 그 결과, 그 문제들을 합쳐서 그 문제의 해답을 얻는다. 일반적으로 많은 문제들은 매우 비슷하다. 이 때문에 다이내믹 플래닝은 각각의 문제들을 한 번만 풀려고 노력하여 계산량을 줄여준다. 주어진 문제들의 해답이 일단 풀리면, 그것을 기억으로 저장해 두어 다음 번에 같은 문제들을 풀 때 직접 짚고 넘어가도록 한다. 이 방법은 반복 문제들의 수에 대해 입력된 규모의 지수가 증가할 때 특히 유용하다.

그리고 그 중 가장 전형적인 것은 배낭 문제입니다.

알고리즘 단계:

1, 최우선 구조 특성. 문제의 최우선 해법이 포함하고 있는 하위 문제의 해법도 최우선이라면, 우리는 이 문제가 최우선 구조 특성 (즉, 최우선화 원칙을 만족하는) 을 가지고 있다고 말한다. 최우선 구조 특성 (최우선 구조 특성) 은 동적 계획 알고리즘 문제 해결에 중요한 단서를 제공한다.

2 , 하위 문제 중복 성질 . 하위 문제 중복 성질은 회귀 알고리즘을 사용하여 위에서 아래로 문제를 해결 할 때, 생성 된 하위 문제는 항상 새로운 문제가 아니며, 일부 하위 문제는 여러 번 반복적으로 계산됩니다 . 동적 계획 알고리즘은 이러한 하위 문제의 중복 성질을 활용하여 각 하위 문제에 대해 한 번만 계산하고 그 계산 결과를 테이블에 저장하고, 이미 계산 된 하위 문제를 다시 계산해야 할 때, 테이블에서 결과를 간단하게 확인하여 높은 효율성을 얻습니다.

• ### 알고리즘 10: 순수 베이시스 분류 알고리즘

순수 베이스 분류 알고리즘은 베이스 이론에 기초한 간단한 확률 분류 알고리즘이다. 베이스 분류의 기초는 확률 추론이다. 즉, 다양한 조건의 존재가 불확실하고, 그 확률이 존재하는 경우에만, 어떻게 추론과 의사결정 작업을 수행할 것인가이다. 확률 추론은 확실성 추론에 대응한다.

순수 베이스 분류기는 정확한 자연 확률 모형을 의존하여 감독 학습 샘플 집중에서 매우 좋은 분류 효과를 얻을 수 있습니다. 많은 실제 응용에서, 순수 베이스 모델의 파라미터는 최대 근접 추정 방법을 사용하여 추정됩니다. 즉, 순수 베이스 모델은 베이스 확률 또는 어떤 베이스 모델을 사용하지 않고 작동합니다.

이러한 단순한 생각과 지나치게 단순화된 가정에도 불구하고, 단순한 베이시스 분류기는 많은 복잡한 현실 상황에서 상당히 좋은 효과를 얻을 수 있다.