알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 말한다. 컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저를 의미한다.

‘알고리즘 (algorithm)’ 이라는 단어는 AD 825년에 ‘Kitab al jabr w’ almuqabala’라는 영향력 있는 수학 교과서를 저술한 9세기 페르시아 수학자 알코와리즘(Abu Ja’far Mohammed ibn Mûsâ al-Khowârizm)의 이름에서 유래한다. 처음에는 더 정확하게 ‘algorism’이라고 표기되었는데 요즈음 ‘algorithm’으로 바뀐 것은 산수라는 의미의 ‘arithmetic’에서 영향을 받은 것 같다. (대수학을 나타내는 ‘algebra’도 위의 책 제목에 등장하는 아랍 단어 ‘al jabr’ 에서 유래한다.) 그러나 알고리즘의 예는 알코와리즘의 책보다 훨씬 이전부터 알려져 왔다. 가장 잘 알려진 예로서 고대 그리스 (기원전 300년경) 시대에 만들어진 두 수의 최대 공약수를 구하는 유클리드 (Euclid) 알고리즘을 들 수 있다.

유한한 단계를 통해 문제를 해결하기 위한 절차나 방법은 원래는 인도에서 아랍을 거쳐 유럽에 보급된 필산(筆算)을 뜻하며 알고리즘은 수학 용어와 컴퓨터 용어 두 가지로 나누어 설명할 수 있다. 먼저 수학 용어로서 알고리즘은 잘 정의되고 명백한 규칙들의 집합 또는 유한 번의 단계 내에서 문제를 풀기 위한 과정이다. 예를 들면, 주어진 정확도에 맞도록 x의 코사인값을 계산하기 위한 대수적인 과정도 알고리즘에 해당한다. 경험적 지식 (heuristic)과 반대되는 용어이다. 컴퓨터 용어로서 알고리즘은 어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다. 알고리즘은 여러 단계의 유한한 집합으로 구성되는데 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. 이때 컴퓨터가 각 연산을 수행하기 위해서는 다음의 조건을 만족해야 한다. ① 명확성 : 각 연산은 명확한 의미가 있어야 한다. ② 효율성 : 각 연산은 원칙적으로 일정한 시간 내에 사람이 연필로 할 수 있어야 한다. ③ 입력 : 외부 입력자료가 있을 수 있다. ④ 출력 : 하나 이상의 결과가 나온다. ⑤ 종결성 : 유한 번의 연산 후에는 끝나야 한다.

300원짜리 커피를 파는 자동판매기의 내부에도 간단한 알고리즘이 있어서, 적합한 금액이 들어오면 크림/설탕의 선택에 따라 따끈한 커피를 내놓고 거스름돈도 정산하여 준다. 높은 아파트에 사는 사람이 출근하려고 엘리베이터 단추를 누르면, 엘리베이터를 작동시키는 알고리즘은 다른 층에 사는 사람이 부르는지 등을 판정하여 적절한 움직임을 한다. 그러나 알고리즘이 부실하게 짜여있으면, 자동판매기가 이상하게 행동하고, 엘리베이터가 고장이 난다. 수학자들이 사용하는 좁은 의미의 알고리즘에 대한 정의는 1930년대에 튜링, 괴델, 처치 등에 의하여 확립되었다. 수학자들은 어떠한 알고리즘이 간단하고, 어떠한 알고리즘이 복잡한가를 이해하기 시작하였다. 그들은 컴퓨터 과학을 탄생시켰으며, 많은 자료에서 원하는 자료를 순식간에 찾아주는 프로그램을 개발하여, 방대한 자료의 인터넷 조사가 가능하도록 하였다. (김홍종 2000)

가장 기본적인 형태의 알고리즘은 체계적 탐색 (systematic search)으로 이것은 모든 가능한 해결 대안들을 포함하고 있으며 체계적으로 차례차례 그것들을 검토해 나간다. 알고리즘은 항상 해법에 도달하도록 해 주지만 불행하게도 어떤 문제들은 (체계적인 탐색처럼) 단지 비효율적인 알고리즘만 있게 되며 커다란 문제에 있어서 이러한 접근은 컴퓨터조차 가혹한 것이 된다. 예를 들면 순회외판원 문제 (Traveling Salesman Problem), 체스 (Chess)에서처럼 알고리즘은 극도의 비효율성을 보여주어 사실상 해결이 불가능해진다. 알고리즘과는 달리 휴리스틱 (Heuristic)은 해결책의 발견을 보장하지 않는다. 그러나 heuristic은 알고리즘보다 효율적이다. 이유는 쓸모없는 대안을 실제 시도하지 않고도 배제할 수 있기 때문이다. (오세진 외, 1999)

훌륭한 알고리즘 중에는 문제를 해결하는 방법과 고속화의 기술에 있어서 공통점을 가진 알고리즘이 많이 있다. 예를 들면 퀵 정렬과 합병 정렬은 정렬 대상이 되는 데이터가 들어 있는 배열을 두 개로 나눠서 두 배열을 각각 정렬한 후, 그들 두 배열을 연결한다는 점에서 공통점을 갖고 있다. 이러한 기본적인 기술을 알고리즘의 설계 기법이라고 부른다. 프로그래머는 해결해야 할 새로운 문제에 접했을 때 기존의 알고리즘 설계 기법을 응용할 수 있는지 어떤지를 생각하는 것은 새로운 알고리즘 개발에 필요한 시간과 경비를 줄일 수 있다는 점에서 매우 중요하다. (박정호, 1995)

간단한 계산 혹은 논리 연산을 하는 튜링 기계가 만들어질 수 있다는 것이 완전히 이해가 된다면 이들을 알고리즘을 수행하는 복잡한 기계를 만드는 데 어떻게 이용할 수 있는지도 쉽게 이해가 될 것이다. 그러한 것을 얼마 동안 실제로 연습해 본 사람이면 이러한 종류의 기계는 어떠한 기계적 작업 (mechanical operation)이라도 수행할 수 있도록 만들 수 있다는 사실을 쉽게 확인할 수 있을 것이다. 수학적으로 말할 때, ‘기계적 작업’이라는 것을 이러한 기계가 수행할 수 있는 작업으로 정의하는 것이 타당성을 갖게 되었다. 이러한 형태의 이론적 기계, 즉 튜링 기계에 의해서 수행될 수 있는 기계적 작업을 수학자들은 ‘알고리즘’이라는 명사와 ‘계산 가능 (computable),’ ‘재귀적 (recursive),’ 혹은 ‘효과적 (effective)’ 이라는 형용사를 사용하여 표현하고 있다. 어떤 계산 과정이 충분히 명료하고 기계적이라면 이를 수행할 수 있는 튜링 기계도 꼭 찾아낼 수 있다는 가정이 설득력이 있게 된 것이다. 이것이 바로 튜링 기계 (Turing Machine) 개념의 동기를 이해하는 데 가장 중요한 사항이다. (Roger Penrose 1989)