지수 알고리즘에서는 일의 양이 유난히 빠르게 늘어난다.
한개의 항목을 추가하면 수행해야 할 일의 양이 두배가 된다 logn 에서는 항목의 수를 두배로 만들어도 일의 단계는 한 개만 늘어나므로 어떤 의미에서 지수 알고리즘은 logn의 알고리즘과 정반대 라고 볼 수 있다.
지수알고리즘은 사실상 모든 가능한 경우를 하나씩 시도해 봐야만 하는 상황에서 발생한다. 특히 암호 기법에 사용되는 알고리즘은 특정 계산 과제를 수행하는 일이 지수 복잡도를 갖도록 하는 데 기반을 둔다.
그런 방법에서는 계산상 실행 불가능할 정도로 큰 N을 선택하여 적의 공격을 방지한다.
실제로 많은 문제나 그런 문제들의 근본이 되는 문제를 해결하려면 지수 알고리즘이 필요하다. 즉, 이러한 문제는 우리가 아는 다항 알고리즘으로는 풀 수 없다. 이를 'NP'문제라고 한다. NP는 비결정적 다항을 의미한다.
이 말은 결정을 내려야 할 때 항상 옳게 추측하는 알고리즘이 있다면 NP문제가 그 알고리즘에 의해 다항 시간 내에 해결될 수 있다는 것이다. 물론 이론적인 개념일 뿐이긴하다.
실제 응용 사례로 여행하는 외판원 문제가 있는데 이 외판원은 자신이 사는 도시에서 출발해 어떤 순서로드 ㄴ다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와ㅑ아 한다. 여기서 목표는 각 도시를 정확히 한번씩 방문하고 전체 여행한 거리를 최소로 만드는 것이다. 이 문제는 통학버스나 쓰레기차가 다니는 경로를 효율적으로 만드는 일과 아이디어가 같다.
>_<