수학 및 컴퓨터 과학에서 알고리즘은 문제의 클래스를 해결하는 방법에 대한 모호하지 않은 사양입니다. 알고리즘은 계산, 데이터 처리 및 자동화 된 추론 작업을 수행 할 수 있습니다.

효과적인 방법으로, 알고리즘은 함수를 계산하기위한 한정된 공간 및 시간 내에서 잘 정의 된 공식 언어로 표현 될 수 있습니다. 초기 상태와 초기 입력 (아마도 비어 있음)부터 시작하여 명령어는 실행될 때 유한 수의 잘 정의 된 연속 상태를 거쳐 결국 “출력”을 생성하고 최종 종료 상태에서 종료하는 계산을 설명합니다. 하나의 상태에서 다음 상태로의 전환이 반드시 결정적이라고는 할 수 없습니다. 무작위 알고리즘으로 알려진 일부 알고리즘에는 무작위 입력이 통합되어 있습니다.

알고리즘의 개념은 수세기 동안 존재 해 왔으며이 개념의 사용은 그리스 수학자들에 귀속 될 수 있습니다. 에라토스테네스의 체와 유클리드의 알고리즘; 알고리즘이라는 용어 자체는 9 세기의 수학자 Muḥammad ibn Mūsā al’Khwārizmī (라틴어로 ‘Algoritmi’)에서 유래되었습니다. 알고리즘의 현대적 관념이 될 부분 형식화는 1928 년 David Hilbert가 제기 한 Entscheidungsproblem ( “결정 문제”)를 풀려고 시도하면서 시작되었다. 이후의 형식화는 “효과적인 계산 가능성”또는 “효과적인 방법”을 정의하려는 시도로 구성되었다. ; 그 공식화에는 1930 년, 1934 년과 1935 년의 Gödel-Herbrand-Kleene 재귀 함수, 1936 년의 Alonzo 교회의 람다 해석, 1936 년의 Emil Post의 Formulation 1, 1936 년과 1939 년의 Alan Turing의 Turing 기계가 포함되었다.

어원
‘알고리즘’이란 단어는 알고리즘에 대한 첫 번째 단계에서 무하마드 이부 알 – 크와 리츠 미 (Muhammad ibn Musa al-Khwarizmi)의 이름을 라틴 화 (latinizing)하는 데 뿌리를두고 있습니다. Al-Khwārizmī (페르시아어 : خوارزمی, 780-850 페이지)는 바그다드의 지혜의 집에서 페르시아 수학자, 천문학 자, 지리학자 및 학자였으며, 그 이름은 ‘Khwarezm’의 일부이며, 그레이터이란은 현재 우즈베키스탄에있다.

약 825 명의 알 Khwarizmi는 Algoritmi de numero Indorum이라는 제목으로 12 세기에 라틴어로 번역 된 힌두 아랍어 숫자 체계에 대한 아랍어 논문을 썼다. 이 제목은 “Algoritmi”가 알 Khwarizmi의 이름의 번역가의 Latinization 인 “인디언의 숫자에 Algoritmi”을 의미합니다. 알 – 크와 리츠 미 (Al-Khwarizmi)는 중세 후기 유럽에서 가장 널리 읽힌 수학자였으며 주로 다른 책인 대수 (Algebra)를 통해 읽 혔다. 중세 후기의 라틴어, 알고리즘론, 영어의 ‘알고리즘 (algorithmism)’, 그의 이름의 부패는 단순히 “10 진수 체계”를 의미했다. 15 세기에 그리스어 ἀρθμός ‘수'( ‘산술’참조)의 영향을 받아 라틴어 단어가 algorithmus로 변경되었으며 해당 영어 용어 ‘알고리즘’이 17 세기에 처음으로 입증되었다. 현대 감각은 19 세기에 도입되었습니다.

영어에서는 1230 년경에 처음 사용되었고, 1391 년에는 초서 (Chaucer)에 의해 사용되었습니다. 영어는 프랑스 용어를 사용했지만, 19 세기 후반까지는 “알고리즘”이 현대 영어에서 갖는 의미를 사용했습니다.

이 단어의 또 다른 초기 사용은 Alexander de Villedieu가 작곡 한 Carmen de Algorismo라는 제목의 매뉴얼에서 1240 년에 나온 것입니다. 그것은 이렇게 시작됩니다 :

기술 / Talibus Indorum fruimur bis quinque figuris에서 기술 및 기술 문서.

이는 다음과 같이 번역됩니다.

알 고리즘은 현재 인도의 인물을 2 번이나 5 번 사용하는 예술입니다.

시는 몇 백 줄 길며 인도 스타일의 새로운 스타일 인 Talibus Indorum 또는 힌두 숫자로 계산하는 기술을 요약합니다.

비공식적 인 정의
“알고리즘”정의에 대한 다양한 관점에 대한 자세한 내용은 알고리즘 특성을 참조하십시오.
비공식적 인 정의는 “일련의 작업을 정확하게 정의하는 일련의 규칙”일 수 있습니다. 여기에는 수치 계산을 수행하지 않는 프로그램을 포함하여 모든 컴퓨터 프로그램이 포함됩니다. 일반적으로 프로그램은 결국 멈출 경우에만 알고리즘입니다.

알고리즘의 원형 예는 두 정수의 최대 공약수를 결정하는 유클리드 알고리즘입니다. 예 (다른 것들도 있음)는 위의 순서도와 이후 섹션에서 예로서 설명됩니다.

Boolos, Jeffrey & 1974, 1999는 다음 인용문에서이 단어의 비공식적 의미를 제시합니다.

인간은 충분히 빠르게, 충분히 길게, 또는 충분히 작게 글자를 쓸 수 없다. († “제한없이 작고 작아 분자, 원자, 전자에 쓰려고 노력할 것”) 모든 몇 가지 표기법에서 그들의 이름을 하나씩 써서 열거 할만큼 무한한 세트. 그러나 인간은 무한대의 무한 집합의 경우 똑같이 유용한 것을 할 수 있습니다. 집합의 n 번째 구성원을 임의의 유한 n에 대해 명시 적으로 지시 할 수 있습니다. 그러한 지시는 컴퓨터 기계가 따르는 형태로, 또는 기호에 대해 아주 기본적인 조작만을 수행 할 수있는 인간에 의해 아주 명료하게 주어져야한다.

“enumerably infinite set”은 정수와 일대일로 대응할 수있는 요소입니다. 따라서 Boolos와 Jeffrey는 알고리즘은 임의의 “입력”정수 또는 이론적으로 임의로 커질 수있는 정수로부터 출력 정수를 “만드는”과정에 대한 지침을 암시한다고 말합니다. 따라서 알고리즘은 y = m + n과 같은 대수 방정식이 될 수 있습니다 – 출력 y를 생성하는 두 개의 임의의 “입력 변수”m 및 n. 그러나 개념을 정의하려는 다양한 저자의 시도는이 단어가 이보다 더 많은 것을 의미한다는 것을 나타냅니다 (추가 예제의 경우).

“컴퓨터”(기계 또는 인간, 필요한 내부적으로 포함 된 정보 및 기능이 갖추어져 있음)의 “이동”을 지정하는 빠르고 효율적인 “올바른”프로세스를위한 정확한 지침 ( “컴퓨터”에서 이해되는 언어) 임의의 입력 정수 / 기호 m 및 n, 기호 + 및 = …을 처리하고 “합리적인”시간에 “지정된 위치 및 지정된 형식의 출력 정수 y를”효과적으로 생성합니다.
알고리즘의 개념은 결정 성의 개념을 정의하는 데에도 사용됩니다. 이 개념은 정식 시스템이 소수의 공리와 규칙 집합에서 시작되는 방법을 설명하기위한 핵심 요소입니다. 논리에서 알고리즘을 완료하는 데 필요한 시간은 측정 할 수 없습니다. 이는 실제 관습에 따라 달라지는 것이 아니기 때문입니다. 진행중인 작업을 특징 짓는 그러한 불확실성 때문에 구체적인 (어떤 의미에서는) 추상 용어 사용에 적합한 알고리즘의 정의를 사용할 수 없게됩니다.

형식화
알고리즘은 컴퓨터가 데이터를 처리하는 방식에 필수적입니다. 많은 컴퓨터 프로그램에는 직원의 월급 계산이나 학생의 성적표 인쇄와 같이 특정 작업을 수행하기 위해 특정 순서로 수행해야하는 특정 지침을 자세히 설명하는 알고리즘이 포함되어 있습니다. 따라서, 알고리즘은 튜링 완료 시스템에 의해 시뮬레이션 될 수있는 임의의 시퀀스의 동작으로 간주 될 수있다. 이 논문을 주장하는 저자로는 Minsky (1967), Savage (1987), Gurevich (2000)가있다.

민스키 : “그러나 우리는 또한”자연적으로 “효과적이라고 할 수있는 절차는 사실 단순한 기계로 실현 될 수 있다고 Turing과 함께 유지할 것입니다. 그것의 호의는 논박하기 어렵다 “.

Gurevich : “Turing의 비공식적 인 논점은 그의 논문에 찬성하여 더 강력한 논문을 정당화합니다. 모든 알고리즘은 Turing 머신에 의해 시뮬레이션 될 수 있습니다 … Savage [1987]에 따르면 알고리즘은 Turing 머신에 의해 정의 된 계산 프로세스입니다” .

일반적으로 알고리즘이 처리 정보와 관련되어 있으면 입력 소스에서 데이터를 읽어서 출력 장치에 쓰고 추후 처리를 위해 저장할 수 있습니다. 저장된 데이터는 알고리즘을 수행하는 엔티티의 내부 상태의 일부로 간주됩니다. 실제로 상태는 하나 이상의 데이터 구조에 저장됩니다.

그러한 계산 프로세스의 경우 알고리즘은 발생할 수있는 모든 가능한 상황에 적용되는 방식으로 지정되는 엄격하게 정의되어야합니다. 즉, 모든 조건부 단계를 체계적으로 처리해야합니다. 각 경우에 대한 기준은 명확해야합니다 (그리고 계산 가능).

알고리즘은 정확한 단계의 정확한 목록이므로 계산 순서는 알고리즘의 기능에 항상 중요합니다. 지침은 일반적으로 명시 적으로 나열된 것으로 가정하고 “위에서부터”시작하여 “아래에서 아래로”, 즉 제어 흐름에 의해 공식적으로 설명되는 아이디어로 설명됩니다.

지금까지 알고리즘의 형식화에 대한이 논의는 명령형 프로그래밍의 전제를 가정했습니다. 이것은 가장 일반적인 개념이며 개별적인 “기계적”수단으로 작업을 설명하려고 시도합니다. 공식화 된 알고리즘에 대한이 개념의 독특한 점은 변수의 값을 설정하는 할당 연산입니다. 그것은 스크래치 패드로서의 “기억”의 직감에서 파생됩니다. 이러한 할당에 대한 예가 아래에 있습니다.

어떤 알고리즘을 구성하는지에 대한 대체 개념에 대해서는 함수 프로그래밍과 논리 프로그래밍을 참조하십시오.

표현 알고리즘
알고리즘은 자연어, 의사 코드, 플로차트, 드래곤 차트, 프로그래밍 언어 또는 제어 테이블 (통역사가 처리하는)을 비롯한 여러 종류의 표기법으로 표현할 수 있습니다. 알고리즘의 자연 언어 표현은 장황하고 모호한 경향이 있으며 복잡하거나 기술적 인 알고리즘에는 거의 사용되지 않습니다. 의사 코드, flowcharts, drakon-charts 및 제어 테이블은 자연 언어 문에 공통적 인 많은 모호함을 피하는 알고리즘을 표현하는 체계적인 방법입니다. 프로그래밍 언어는 주로 컴퓨터에서 실행될 수있는 형태로 알고리즘을 표현하기위한 것이지만 종종 알고리즘을 정의하거나 문서화하는 방법으로 사용됩니다.

가능한 다양한 표현이 가능하며 주어진 Turing 머신 프로그램을 순서도와 drakon-charts와 같이 머신 테이블의 시퀀스 (유한 상태 머신, 상태 전이 테이블 및 제어 테이블)에서 표현할 수 있습니다 (자세한 내용은 상태 다이어그램), 또는 “quadruples”세트라는 초보적인 기계 코드 또는 어셈블리 코드의 형태로 사용할 수 있습니다 (자세한 내용은 튜링 기계 참조).

알고리즘 표현은 Turing machine description의 세 가지 허용 수준으로 분류 할 수 있습니다.

1 높은 수준의 설명
“… 구현 세부 사항을 무시하고 알고리즘을 설명하는 산문.이 수준에서는 기계가 테이프 또는 헤드를 어떻게 관리하는지 언급 할 필요가 없습니다.”
2 구현 설명
“… Turing 기계가 머리를 사용하는 방식과 테이프에 데이터를 저장하는 방식을 정의하는 데 사용되는 산문입니다.이 수준에서는 상태 나 전환 기능에 대한 세부 정보를 제공하지 않습니다.”
3 정식 설명
가장 세부적인 “최저 레벨”은 튜링 머신의 “상태 테이블”을 제공합니다.
세 가지 레벨 모두에 설명 된 간단한 알고리즘 “Add m + n”의 예제는 알고리즘 # 예제를 참조하십시오.

이행
대부분의 알고리즘은 컴퓨터 프로그램으로 구현됩니다. 그러나 알고리즘은 생물학적 신경망 (예 : 산술을 구현하는 뇌 또는 음식을 찾는 곤충), 전기 회로 또는 기계 장치와 같은 다른 수단으로도 구현됩니다.

컴퓨터 알고리즘
컴퓨터 시스템에서 알고리즘은 기본적으로 주어진 “목표”컴퓨터가 주어진 입력 (아마도 null) 입력으로부터 출력을 생성하는 데 소프트웨어 개발자가 소프트웨어로 작성한 논리의 인스턴스입니다. 오래된 하드웨어에서 실행되는 최적의 알고리즘은보다 효율적인 하드웨어에서 실행되는 동일하지 않은 (더 높은 시간 복잡도) 알고리즘보다 빠른 결과를 산출합니다. 그런 이유로 컴퓨터 하드웨어와 같은 알고리즘이 기술로 간주됩니다.

“우아한”(조밀 한) 프로그램, “좋은”(빠른) 프로그램 : “단순함과 우아함”이라는 개념은 크누 틴에서, 그리고 정확하게 Chaitin에서 비공식적으로 나타납니다.

크 누스 : “느슨하게 정의 된 미학적 감각으로 좋은 알고리즘을 원한다.”하나의 기준은 알고리즘을 수행하는 데 걸리는 시간이다. … 다른 기준은 컴퓨터의 알고리즘 적응성, 단순성 및 우아함이다 , 등 ”
Chaitin : “… 프로그램은 ‘우아하다’는 말로 표현하자면, 그것이 가능한 출력을 생산하는 가장 작은 프로그램이라는 것을 의미한다”
Chaitin은 자신의 정의를 다음과 같이 서술합니다. “프로그램이 ‘우아함’임을 증명할 수 없다는 것을 보여줄 것입니다. – 그런 증거는 Halting 문제를 해결할 것입니다.

알고리즘에 따라 계산 가능한 알고리즘 대 함수 : 주어진 함수에 대해 여러 알고리즘이 존재할 수 있습니다. 프로그래머가 사용할 수있는 명령어 세트를 확장하지 않은 경우에도 마찬가지입니다. Rogers는 “알고리즘의 개념, 즉 절차와 알고리즘에 의해 계산 가능한 함수의 개념, 즉 절차에 의해 산출 된 매핑의 개념을 구별하는 것이 중요합니다. 동일한 함수에는 여러 가지 알고리즘이있을 수 있습니다.”

불행히도 선량 (속도)과 우아함 (컴팩트 함) 사이에는 트레이드 오프가있을 수 있습니다. 우아한 프로그램은 덜 우아함보다 계산을 완료하는 데 더 많은 단계를 취할 수 있습니다. 유클리드의 알고리즘을 사용하는 예가 아래와 같습니다.

컴퓨터 (및 컴퓨터), 계산 모델 : 컴퓨터 (또는 사람의 “컴퓨터”)는 제한된 유형의 기계, 지시를 맹목적으로 따르는 “이산 결정 론적 기계 장치”입니다. Melzak과 Lambek의 원시 모델은이 개념을 (i) 이산적이고 구별 가능한 위치, (ii) 분리 된, 구별 할 수없는 카운터 (iii) 대리인, (iv) 에이전트.

알고리즘의 시뮬레이션 : 컴퓨터 (컴퓨터) 언어 : Knuth는 “알고리즘을 배우는 가장 좋은 방법은 그것을 시도하고 즉각적으로 펜과 종이를 가져 와서 예제를 통해 작업하는 것”이라고 독자들에게 조언합니다. 그러나 실제 상황을 시뮬레이션하거나 실행하면 어떨까요? 프로그래머는 알고리즘을 시뮬레이터 / 컴퓨터 / 컴퓨터가 효과적으로 실행할 수있는 언어로 번역해야합니다. 스톤 (Stone)은 이것을 예로 들었습니다. 2 차 방정식의 근원을 계산할 때 계산자는 제곱근을 취하는 방법을 알아야합니다. 알고리즘이 유효하지 않다면 알고리즘은 제곱근을 추출하기위한 규칙 집합을 제공해야합니다.

즉, 프로그래머는 대상 컴퓨팅 에이전트 (컴퓨터 / 컴퓨터)에 상대적으로 효과적인 “언어”를 알아야합니다.

알고리즘 분석
주어진 알고리즘에 이론적으로 얼마나 많은 특정 리소스 (시간 또는 저장 공간)가 필요한지를 아는 것이 중요합니다. 그러한 정량적 인 답 (추정치)을 얻기위한 알고리즘 분석을위한 방법이 개발되었다. 예를 들어 위의 정렬 알고리즘에는 O (n)의 시간 요구 사항이 있습니다. n의 큰 O 표기법을 목록의 길이로 사용합니다. 항상 알고리즘은 두 개의 값, 즉 지금까지 발견 된 최대 수와 입력 목록의 현재 위치를 기억하면됩니다. 따라서 입력 된 숫자를 저장하는 데 필요한 공간이 계산되지 않은 경우 O (1)의 공간 요구 사항이 있거나 계산 된 경우 O (n)이 필요합니다.

형식적 대 경험적
알고리즘의 분석과 연구는 컴퓨터 과학의 분야이며, 특정 프로그래밍 언어 나 구현을 사용하지 않고 추상적으로 실행됩니다. 이러한 의미에서 알고리즘 분석은 알고리즘의 기본 특성에 초점을 맞추고 특정 구현의 특성에 초점을 맞추지 않는다는 점에서 다른 수학적 분야와 유사합니다. 일반적으로 의사 코드는 가장 단순하고 가장 일반적인 표현이므로 분석에 사용됩니다. 그러나 궁극적으로 대부분의 알고리즘은 일반적으로 특정 하드웨어 / 소프트웨어 플랫폼에서 구현되며 알고리즘 효율성은 결국 실제 코드를 사용하여 테스트됩니다. “일회성”문제의 해결을 위해, 특정 알고리즘의 효율성은 (n이 극단적으로 큰 경우를 제외하고) 중요한 결과를 가져 오지 않을 수도 있지만, 빠른 대화 형, 상업용 또는 장수명의 과학적 사용을 위해 설계된 알고리즘의 경우 중요 할 수 있습니다. 작은 n에서 큰 n으로 스케일링하는 것은 자주 그렇지 않은 비효율적 인 알고리즘을 노출시킵니다.

실행 효율성
잘 정립 된 알고리즘에서도 가능한 개선 가능성을 설명하기 위해 FFT 알고리즘 (이미지 프로세싱 분야에서 많이 사용됨)과 관련된 최근의 중요한 혁신은 의학 이미징과 같은 애플리케이션에서 처리 시간을 최대 1,000 배까지 감소시킬 수 있습니다. 일반적으로 속도 향상은 문제의 특수한 특성에 달려 있으며 실제 응용 프로그램에서는 매우 일반적입니다. 이 크기의 속도가 빨라짐에 따라 디지털 카메라 및 의료 장비와 같은 이미지 처리를 광범위하게 사용하는 컴퓨팅 장치에서 전력 소비를 줄일 수 있습니다.

분류
알고리즘을 분류하는 방법에는 여러 가지가 있으며 각 알고리즘마다 고유 한 장점이 있습니다.

구현 방식
알고리즘을 분류하는 한 가지 방법은 구현 수단입니다.

재귀
재귀 알고리즘은 특정 조건 (종료 조건이라고도 함)이 일치 할 때까지 반복적으로 자체를 호출 (참조를 작성)하는 알고리즘으로, 함수 프로그래밍에 공통적 인 방법입니다. 반복 알고리즘은 루프와 같은 반복적 인 구조를 사용하고 때로는 스택과 같은 추가 데이터 구조를 사용하여 주어진 문제를 해결합니다. 일부 문제는 당연히 하나의 구현 또는 다른 구현에 적합합니다. 예를 들어, 하노이의 탑은 재귀 구현을 통해 잘 이해됩니다. 모든 재귀 버전에는 동등한 버전이 있지만 반복 버전은 반복 버전입니다.

논리적 인
알고리즘은 통제 된 논리적 공제로 간주 될 수 있습니다. 이 개념은 다음과 같이 표현 될 수 있습니다 : 알고리즘 = 논리 + 제어. 논리 구성 요소는 계산에 사용될 수있는 공리를 나타내고 제어 구성 요소는 공리에 공제가 적용되는 방식을 결정합니다. 이것은 논리 프로그래밍 패러다임의 기초입니다. 순수한 논리 프로그래밍 언어에서 제어 구성 요소는 고정되어 있고 알고리즘은 논리 구성 요소 만 제공하여 지정됩니다. 이 접근법의 매력은 우아한 의미입니다 : 공리의 변화는 알고리즘에 잘 정의 된 변화를 가지고 있습니다.

직렬, 병렬 또는 분산
알고리즘은 컴퓨터가 알고리즘의 한 명령을 한 번에 실행한다는 가정하에 주로 논의됩니다. 이러한 컴퓨터를 직렬 컴퓨터라고도합니다. 이러한 환경을 위해 설계된 알고리즘을 병렬 알고리즘 또는 분산 알고리즘과 달리 직렬 알고리즘이라고합니다. 병렬 알고리즘은 여러 프로세서가 동시에 문제를 해결할 수있는 컴퓨터 아키텍처를 활용하지만 분산 알고리즘은 컴퓨터 네트워크와 연결된 여러 컴퓨터를 사용합니다. 병렬 또는 분산 알고리즘은 문제를 더 대칭 또는 비대칭 하위 문제로 나누고 결과를 다시 수집합니다. 이러한 알고리즘의 리소스 소비는 각 프로세서의 프로세서 사이클뿐만 아니라 프로세서 간의 통신 오버 헤드입니다. 일부 정렬 알고리즘은 효율적으로 병렬화 될 수 있지만 통신 오버 헤드는 비쌉니다. 반복 알고리즘은 일반적으로 병렬 처리가 가능합니다. 일부 문제에는 병렬 알고리즘이 없으며 본질적으로 직렬 문제라고합니다.

결정 성 또는 비 결정적
결정 론적 알고리즘은 알고리즘의 모든 단계에서 정확한 결정으로 문제를 해결하지만 비 결정적 알고리즘은 추측을 통해 문제를 해결하지만 추론은 휴리스틱을 사용하여 더 정확한 추측을합니다.

정확하거나 근사치
많은 알고리즘이 정확한 솔루션에 도달하는 동안 근사 알고리즘은 실제 솔루션에 가까운 근사값을 찾습니다. 근사는 확정적 또는 무작위 전략을 사용하여 도달 할 수 있습니다. 이러한 알고리즘은 많은 어려운 문제에 실질적인 가치가 있습니다. 근사 알고리즘의 예 중 하나가 배낭 문제입니다. 배낭 문제는 주어진 항목 세트가있는 경우 문제가됩니다. 문제의 목표는 최대 총 가치를 얻기 위해 배낭을 포장하는 것입니다. 각 항목에는 약간의 가중치가 있습니다. 우리가 수행 할 수있는 총 무게는 고정 된 숫자 X 이상입니다. 따라서 항목의 가중치와 그 값을 고려해야합니다.

양자 알고리즘
그들은 양자 계산의 현실적인 모델을 실행합니다. 이 용어는 대개 본질적으로 보이는 알고리즘에 사용되거나 양자 중첩 또는 양자 얽힘과 같은 양자 계산의 필수 기능을 사용합니다.

디자인 패러다임으로
알고리즘을 분류하는 또 다른 방법은 설계 방법론 또는 패러다임에 의한 것입니다. 각각 다른 패러다임이 존재합니다. 또한, 이들 범주 각각은 많은 다른 유형의 알고리즘을 포함합니다. 몇 가지 일반적인 패러다임은 다음과 같습니다.

무차별적인 검색 또는 철저한 검색
이것은 최선의 해결책을 찾기 위해 모든 가능한 해결책을 시도하는 순진한 방법입니다.

분열과 정복
나누기 및 정복 알고리즘은 문제가 쉽게 해결 될 정도로 인스턴스가 작아 질 때까지 같은 문제의 하나 이상의 작은 인스턴스 (일반적으로 재귀 적으로)로 문제의 인스턴스를 반복적으로 축소합니다. 분할 및 정복의 한 가지 예는 병합 정렬입니다. 정렬은 데이터를 세그먼트로 나누고 각 세그먼트를 병합하여 정복 단계에서 전체 데이터를 정렬 한 후에 각 데이터 세그먼트에서 정렬 할 수 있습니다. 분할 및 정복의 간단한 변형은 감소 및 정복 알고리즘이라고하며, 동일한 하위 문제를 해결하고이 하위 문제의 해결 방법을 사용하여 더 큰 문제를 해결합니다. 분할 및 정복은 여러 가지 하위 문제로 문제를 나누기 때문에 정복 단계는 감소 및 정복 알고리즘보다 복잡합니다. 감소 및 정복 알고리즘의 예는 2 진 검색 알고리즘입니다.

검색 및 열거
체스 게임과 같은 많은 문제는 그래프상의 문제로 모델링 할 수 있습니다. 그래프 탐색 알고리즘은 그래프 주위를 이동하는 규칙을 지정하며 이러한 문제에 유용합니다. 이 범주에는 검색 알고리즘, 분기 및 바운드 열거 및 역 추적도 포함됩니다.
무작위 알고리즘

복잡성 감소
이 기술은 어려운 문제를 잘 알려진 문제로 변환하여 해결합니다.이 문제는 우리가 (잘하면) 점근 적으로 최적의 알고리즘을 가지고 있습니다. 목표는 알고리즘의 복잡성이 감소 된 알고리즘에 의해 좌우되지 않는 감소 알고리즘을 찾는 것입니다. 예를 들어, 정렬되지 않은 목록에서 중앙값을 찾는 하나의 선택 알고리즘은 먼저 목록 (비싼 부분)을 정렬 한 다음 정렬 된 목록의 중간 요소 (값싼 부분)를 가져옵니다. 이 기술은 변환 및 정복이라고도합니다.

최적화 문제
최적화 문제에는 알고리즘의보다 구체적인 분류가 있습니다. 이러한 문제에 대한 알고리즘은 위에서 설명한 하나 이상의 일반 범주뿐만 아니라 다음 중 하나에 속할 수 있습니다.

선형 프로그래밍
선형 평등 및 부등식 제약 조건에 바인딩 된 선형 함수에 대한 최적 솔루션을 검색 할 때 문제의 제약 조건을 사용하여 최적 솔루션을 직접 생성 할 수 있습니다. 이 카테고리의 모든 문제를 해결할 수있는 알고리즘이 있습니다 (예 : 인기있는 심플 렉스 알고리즘). 선형 프로그래밍으로 해결할 수있는 문제는 유향 그래프의 최대 흐름 문제를 포함합니다. 문제가 추가로 하나 이상의 미지수가 정수 여야 함을 요구하면 정수 프로그래밍으로 분류됩니다. 선형 프로그래밍 알고리즘은 정수 값에 대한 모든 제한이 피상적 인 것으로 입증 될 수있는 경우, 즉 솔루션이 이러한 제한을 어쨌든 충족시키는 경우 이러한 문제를 해결할 수 있습니다. 일반적인 경우, 문제의 난이도에 따라 근사해를 구하는 특수 알고리즘 또는 알고리즘이 사용됩니다.
동적 프로그래밍

문제가 최적의 하부 구조를 나타낼 때 – 문제에 대한 최적의 솔루션이 하위 문제에 대한 최적의 솔루션과 중복되는 하위 문제로 구성 될 수 있음을 의미합니다. 동일한 하위 문제가 여러 문제 인스턴스를 해결하는 데 사용됨을 의미하는 동적 프로그래밍이라는 더 빠른 접근법은 이미 계산되었습니다. 예를 들어 Floyd-Warshall 알고리즘은 모든 인접한 정점의 목표에 대한 최단 경로를 사용하여 가중 그래프의 정점에서 목표로가는 최단 경로를 찾을 수 있습니다. 동적 프로그래밍과 메모가 함께 진행됩니다. 동적 프로그래밍과 분할 및 정복 간의 주된 차이점은 하위 문제가 동적으로 프로그래밍에서 겹치는 반면 하위 문제는 분할 및 정복에서 다소 독립적이라는 것입니다. 동적 프로그래밍과 간단한 재귀 간의 차이점은 재귀 호출의 캐싱 또는 메모 작성에 있습니다. 하위 문제가 독립적이며 반복이없는 경우 메모 작성이 도움이되지 않습니다. 따라서 동적 프로그래밍은 모든 복잡한 문제에 대한 해결책이 아닙니다. 메모 프로그래밍을 사용하거나 이미 해결 된 하위 문제 테이블을 유지함으로써 동적 프로그래밍은 많은 문제의 지수 적 특성을 다항식 복잡성으로 감소시킵니다.

욕심쟁이 방법
그리 디 알고리즘은 동적 프로그래밍 알고리즘과 유사하지만 하부 구조를 검토함으로써 작동합니다.이 경우 문제가 아니라 주어진 솔루션입니다. 이러한 알고리즘은 어떤 방법으로 구성되거나 제공 될 수있는 몇 가지 솔루션으로 시작하여 작은 수정을 통해이를 향상시킵니다. 일부 문제의 경우 최적의 솔루션을 찾을 수있는 반면 다른 알고리즘은 로컬 최적화에서 중지합니다. 즉 알고리즘으로는 개선 할 수는 없지만 최적이 아닌 솔루션에서는 중지합니다. greedy 알고리즘의 가장 보편적 인 사용은이 방법으로 최적의 솔루션을 찾는 것이 가능한 최소 스패닝 트리를 찾는 것입니다. Huffman Tree, Kruskal, Prim, Sollin은 이러한 최적화 문제를 해결할 수있는 욕심 많은 알고리즘입니다.

경험적 방법
최적화 문제에서 최적의 솔루션을 찾는 것이 비실용적 인 경우 휴리스틱 알고리즘을 사용하여 최적의 솔루션에 가까운 솔루션을 찾을 수 있습니다. 이러한 알고리즘은 작업이 진행됨에 따라 최적의 솔루션에 더 가까워지면서 작동합니다. 원칙적으로 무한한 시간 동안 실행하면 최적의 솔루션을 찾을 수 있습니다. 그들의 장점은 비교적 짧은 시간 내에 최적의 솔루션에 매우 근접한 솔루션을 찾을 수 있다는 것입니다. 이러한 알고리즘에는 지역 검색, 금식 검색, 시뮬레이션 어닐링 및 유전 알고리즘이 포함됩니다. 시뮬레이션 된 어닐링과 같은 일부 알고리즘은 비 결정적 알고리즘이지만 다른 알고리즘 (예 : 검색)은 결정적입니다. 비 최적 해의 오차에 대한 한계가 알려지면 알고리즘은 근사 알고리즘으로 더 분류됩니다.

연구 분야별
모든 과학 분야에는 고유 한 문제가 있으며 효율적인 알고리즘이 필요합니다. 한 분야의 관련 문제는 종종 함께 연구됩니다. 일부 예제 클래스는 검색 알고리즘, 정렬 알고리즘, 병합 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 계산 기하학 알고리즘, 조합 알고리즘, 의료 알고리즘, 기계 학습, 암호화, 데이터 압축 알고리즘 및 파싱 기술입니다.

필드는 서로 중첩되는 경향이 있으며, 한 필드에서의 알고리즘 향상은 다른 필드의 알고리즘 향상을 가져올 수 있습니다. 예를 들어, 동적 프로그래밍은 산업에서의 자원 소비 최적화를 위해 개발되었지만 이제는 많은 분야에서 광범위한 문제를 해결하는 데 사용됩니다.

복잡성으로
알고리즘은 입력 크기와 비교하여 완료해야하는 시간으로 분류 할 수 있습니다.

일정 시간 : 알고리즘에 필요한 시간이 입력 크기에 관계없이 동일하면 예 : 배열 요소에의 액세스
선형 시간 : 시간이 입력 크기에 비례하면. 예 : 리스트의 트래버스.
Logarithmic time (로그 시간) : 시간이 입력 크기의 대수 함수 인 경우. 예 : 이진 검색 알고리즘.
다항식 시간 (Polynomial time) : 시간이 입력 크기의 거듭 제곱이면. 예 : 버블 정렬 알고리즘은 2 차 시간 복잡성을 갖는다.
지수 시간 : 시간이 입력 크기의 지수 함수이면. 예 : 무차별 공격 검색.
일부 문제에는 복잡성이 다른 여러 알고리즘이 있고 다른 문제에는 알고리즘이 없거나 효율적인 알고리즘이 알려져 있지 않을 수 있습니다. 또한 일부 문제에서 다른 문제로의 매핑이 있습니다. 이로 인해 알고리즘 대신 문제 자체를 가능한 최상의 알고리즘의 복잡성을 기반으로 등가 클래스로 분류하는 것이 더 적합하다는 것이 발견되었습니다.

연속 알고리즘
형용사 “연속”은 “알고리즘”이라는 단어에 적용될 때 다음을 의미 할 수 있습니다.

이 데이터가 불연속 근사로 표시 되더라도 연속 수량을 나타내는 데이터에서 작동하는 알고리즘 – 이러한 알고리즘은 수치 해석으로 연구됩니다. 또는
아날로그 컴퓨터에서 실행되는 데이터에서 계속 작동하는 미분 방정식 형태의 알고리즘입니다.