10개 도시를 최단 거리로 여행하는 법

알고리즘 '복잡도' 또는 실행 시간의 스펙트럼을 따라가며 몇 가지 알고리즘을 살펴봤다. 먼저 효율이 높은 알고리즘으로는 logN의 복잡도를 갖는 이진 검색 등이 있는데, 데이터의 양이 증가함에 따라 일의 양이 천천히 늘어난다. 가장 일반적인 경우는 선형, 즉 단순히 N의 복잡도를 가지며, 일의 양이 데이터 양에 정비례한다. 퀵 정렬 같은 알고리즘은 NlogN의 복잡도를 갖는데 N보다는 효율이 낮지만(일이 양이 더 빨리 증가하지만), 로그 인자가 상당히 느리게 증가하므로 큰 N 값에도 대단히 효과적으로 활용할 수 있다. 다음으로 N², 즉 2차는 일의 양이 너무 빨리 늘어나서 실행하기 고역스러운 수준이거나 아예 활용 불가능한 수준 그 사이에 있다.

 이 밖에 다른 복잡도를 갖는 알고리즘도 많고, 몇 가지는 이해하기 어렵지 않다. 예컨대 N³, 즉 3차는 2차보다 효율이 낮지만 발상은 같다. 다른 복잡도 개념은 너무 심오해서 전문가들만 관심을 가지는 정도다. 하지만 한 가지는 알고 넘어갈 만한데, 실생활에서 자주 등장하지만 효율이 특히 낮고 중요하기 때문이다. 이는 지수 복잡도로 2ⁿ의 비율로 증가한다, 지수 알고리즘에서 일의 양이 유난히 빠르게 늘어난다. 한 개의 항목을 추가하면 수행해야 할 일의 양이 두배가 된다 logN에 의미에서 지수 알고리즘은 logN 알고리즘과 정반대라고 볼 수 있다.

 지수 알고리즘은 사실상 모든 가능한 경우를 하나씩 시도해 봐야만 하는 상황에서 발생한다. 다행히도 지수 알고리즘이 필요한 문제가 있기에 긍정적인 면도 있다. 몇몇 알고리즘, 특히 암호 기법에 사용되는 알고리즘은 특정 계산 과제를 수행하는 일이 지수 복잡도를 갖도록 하는 데 기반을 둔다. 그런 알고리즘을 활용할 때는 은밀한 지름길을 모르고서는 문제를 바로 푸는 일이 계산상 실행 불가능할 정도로 큰 N을 선택하여 적의 공격을 방지한다. 

 지금쯤 여러분은 어떤 문제는 처리하기 쉽지만, 다른 문제는 더 어려워 보인다는 것을 직관적으로 이해했을 것이다. 더 정확하게 구분하는 방법이 있다. '쉬운' 문제는 복잡도 면에서 '다항'이다. 즉 실행 시간이 N² 같은 어떤 다항식으로 표현되는데, 만일 지수가 2보다 크면 적용하기 어려울 수 있다(다항식이 뭔지 잊어버렸더라도 걱정하지 마라, 여기서는 단순히 N²이나 N³ 같은 어떤 변수의 정수 거듭제곱 꼴로 생각하면 된다). 컴퓨터과학자들은 이러한 부류의 문제를 '다항'을 의미하는 'P'라고 부르는데, 다항 시간 내에 해결할 수 있기 때문이다.

 실제로 발생하는 많은 문제나 그런 문제들의 근본이 되는 문제를 해결하려면 지수 알고리즘이 필요하다. 즉 이러한 문제는 우리가 아는 다항 알고리즘으로는 풀 수 없다. 이를 'NP' 문제라고 한다. NP 문제는 해결책을 빨리 찾을 수는 없지만, 어떤 해결책을 알고 있다면 그것이 맞는지는 빨리 입증할 수 있다. NP는 '비결정적 다항'을 의미한다. 이 말은 결정을 내려야 할 때 항상 옳게 추측하는 알고리즘이 있다면 NP 문제가 그 알고리즘에 의해 다항 시간 내에 해결될 수 있다는 뜻이다. 현실에서는 항상 올바른 선택을 할 정도로 운이 좋은 경우는 거의 없으므로 이는 단지 이론적인 개념일 뿐이다.

 가능한 모든 해법을 완전 탐색하는 것보다 더 효율적으로 풀 방법이 없다는 말이다. 이는 알고리즘을 연구하는 사람들에게 좌절감을 준다. 문제가 본질적으로 난해해서인지, 아니면 우리가 덜 똑똑해서 아직 해결책을 알아내지 못한 것인지 모르겠지만, 오늘날에는 본질적으로 난해하기 때문인 것으로 의견이 기울고 있다.

 1971년에 스티븐 쿡이 놀라운 수학적 연구 결과를 발표했다. 그는 이런 문제 중 다수가 서로 동등하다는 것을 증명했다. 만일 우리가 그 문제 중 어느 한 문제를 해결하는 다항 시간 알고리즘을 찾을 수 있다면, 이 모든 문제에 대한 다항 시간 알고리즘을 찾아낼 수 있다는 것이다.

2000년에 클레이 수학 연구소는 일곱 가지 미해결 문제에 대해 문제 하나당 100만 달러의 상금을 걸었다. 이 가운데 하나는 P가 NP와 같은지 밝히는 것으로, 다시 말하자면 난해 문제가 쉬운 문제와 정말로 같은 부류인지 증명하는 문제다. 또 다른 문제인 푸앵카레 추측은 1900년대 초에 등장했다. 이 문제는 러시아 수학자인 그리고리 페렐만이 풀었고 2010년에 상이 수여됐지만 페렐만은 수상을 거절했다. 지금은 여섯 문제 남았다

 이런 종류의 복잡도를 다룰 때 명심해야 할 점이 몇 가지 있다. P = NP 문제가 중요하기는 하지만 현실적인 사한이라기보다는 이론적인 주제다.

 컴퓨터과학자가 말하는 복잡도란 대부분 최악의 경우에 대한 것이지만 보통은 최악의 경우까지 가지 않는다. 다시 말해, 어떤 문제는 답을 계산하는 데 극한의 시간이 필요하겠지만 모든 문제를 그렇게 난해하게 접근할 필요는 없다. 또한 복잡도의 결과는 N이 큰 값일 때만 적용되는 점근적 척도다. 현실에서는 이러한 점근적 작동 방식이 문제가 되지 않을 정도로 N이 작을 수도 있다. 예를 들어 수십 또는 수백 개의 항목만 정렬한다고 생각해 보자. 복잡도가 2차인 선택 정렬은 NlogN 인 퀵 정렬보다 점근적으로는(즉 항목의 수가 무한대에 가까워지는 것을 가정한 척도에서는) 훨씬 효율이 낮다. 하지만 이 주어진 작업에 대해서는 실행 속도가 충분히 빠를 수 있다.