알고리즘

로그아웃한 편집자를 위한 문서 더 알아보기

둘러보기

사용자 모임

편집 안내

도구

인쇄/내보내기

다른 프로젝트

알고리즘(영어: algorithm), 셈법수학컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다.

알고리즘은 연산, 데이터 마이닝(기계 학습) 또는 자동화된 추론을 수행한다.

산법(算法), 셈법, 계산절차(計算節次)라고도 한다.

알고리즘은 9세기 페르시아의 수학자인 무함마드 알콰리즈미의 이름을 라틴어화한 알고리스무스(Algorismus)에서 유래한 표현이다.

영어로 Algorithm의 발음 기호는 /ˈælɡəˌɹɪðəm/ 또는 /ˈælɡəˌɹɪðm̩/이며 Algorithm을 '알고리즘'으로 표기하는 것은 This를 '지스'로, Rhythm /rɪðəm/을 '리즘'으로 표기하는 것과 마찬가지의 잘못된 것이라는 주장이 있다. 하지만 실제 생활에서는 알고리즘이라는 표기가 알고리듬이라는 표기에 비해 압도적으로 많이 사용되고 있다.[1]

멈춤문제의 결과로 알고리즘멈추기까지 걸리는 시간을 일반적으로 측정할 수 없다.

그러므로 알고리즘에 대해 단순한 직관을 만족하는 형식적인 정의는 불가능하다.

따라서 알고리즘의 공식적인 정의는 없다.

대부분의 알고리즘은 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의한다. 다음은 좋은 알고리즘의 특징이다.

알고리즘은 자연어, 의사코드, 순서도, 프로그래밍언어, 인터프리터가 작업하는 제어테이블, 유한상태기계상태도 등으로 표현할 수 있다. 다음은 알고리즘 개발의 정형적인 단계이다.

알고리즘을 설계하는 기술에는 운용과학의 방법, 설계짜임새를 써먹는 방법 등이 있다. 대부분의 알고리즘은 컴퓨터 프로그램으로 구현되지만, 전기 회로생물학신경회로를 사용하기도 한다.

입력의 크기가 일 경우, 점근 표기법 를 사용하여 다음과 같이 나타낸다.

대문자 O 표기법의 정의상 아래의 복잡도는 그 위의 복잡도를 포함하므로, 대부분의 알고리즘은 의 수행 시간을 가진다.

가장 단순한 알고리즘 가운데 하나는 임의로 나열된 숫자들 가운데 가장 큰 수를 찾는 것이다. 다음은 목록 안에 있는 모든 수를 살펴보는 알고리즘이다.

퀵 정렬 알고리즘