지수 시간 복잡도 (exponential time complexity)

한 줄 정의: 입력 크기 n이 커질수록 실행 시간이 2^n이나 n! 같은 지수 함수 형태로 증가하는 알고리즘의 시간 복잡도.

쉽게 풀면

지수 시간 알고리즘은 입력이 조금만 커져도 실행 시간이 폭발적으로 늘어난다. 예를 들어 입력 크기가 1 늘어날 때마다 실행 시간이 두 배가 되는 식이다. 입력 크기 20 정도면 순식간에 끝나던 것이 입력 크기 60만 되어도 슈퍼컴퓨터로도 우주의 나이보다 오래 걸릴 수 있다. 많은 NP-난해 문제의 무차별 대입(brute-force) 해법이 이런 지수 시간을 가진다.

왜 중요한가

지수 시간 복잡도는 어떤 문제를 정확히 풀 수는 있어도 "실용적으로 풀 수 있는가"를 가르는 경계선 역할을 합니다. 알고리즘 논문에서 새로운 방법을 제안할 때 기존 무차별 대입 해법이 지수 시간이라는 점을 지적하고, 이를 다항 시간이나 더 나은 지수 밑(base)으로 개선했다는 식으로 기여를 강조하는 경우가 많습니다. 또한 NP-난해 문제의 근사 알고리즘, 휴리스틱, 매개변수화 복잡도 연구 전반의 출발점이 되는 개념입니다.

논문에서는 이렇게 쓰입니다

"무차별 대입 방식은 O(2^n)의 지수 시간이 소요되어 n이 30을 넘으면 현실적으로 계산이 불가능하다."

정확해를 구하는 알고리즘의 비현실성을 지적하고 근사 알고리즘이나 휴리스틱의 필요성을 정당화할 때 쓰인다.

"제안한 분기 한정 기법은 여전히 최악의 경우 지수 시간이지만, 실제 벤치마크 인스턴스에서는 기존 완전 탐색 대비 탐색 공간을 크게 줄였다."

이론적 최악의 경우 복잡도는 개선되지 않았더라도 실용적 성능이 향상되었음을 보이는 조합 최적화 논문에서 흔한 표현이다.

"고정 매개변수 k에 대해 지수 시간을 갖지만 입력 크기 n에 대해서는 다항 시간인 알고리즘을 설계함으로써 매개변수화 복잡도 관점에서의 다루기 쉬움(tractability)을 보였다."

매개변수화 복잡도 이론 논문에서, 전체적으로는 지수 시간이라도 특정 매개변수에 대해서만 지수적으로 증가하도록 복잡도를 분리해 설계한 사례다.

조금 더 깊게 보면

지수 시간이라고 해도 밑(base)의 크기에 따라 실제 체감 성능은 크게 달라지며, 2^n과 1.1^n은 이론적으로 모두 지수 함수이지만 실무에서의 처리 가능 범위는 전혀 다릅니다. 이 때문에 알고리즘 연구에서는 지수 밑을 조금이라도 줄이는 것 자체가 중요한 기여로 평가되기도 합니다. 또한 매개변수화 복잡도 이론에서는 전체 입력 크기가 아니라 특정 매개변수에 대해서만 지수적으로 증가하는 FPT(fixed-parameter tractable) 알고리즘을 설계함으로써, 실제로 문제되는 매개변수 값이 작은 경우 지수 시간 문제를 현실적으로 다룰 수 있게 만드는 접근도 자주 쓰입니다.

주의할 점

지수 시간이라고 항상 실제로 느린 것은 아니며, 입력 크기가 아주 작은 경우에는 오히려 상수 계수가 작은 지수 알고리즘이 다항 알고리즘보다 빠를 수도 있다.