계산 복잡도
From Wikipedia, the free encyclopedia
컴퓨터 과학에서 알고리즘의 계산 복잡도(計算複雜度, computational complexity) 또는 단순히 복잡도(complexity)는 알고리즘을 실행하는 데 필요한 자원의 양이다. 특히 계산 시간(일반적으로 필요한 기본 연산의 수로 측정)과 메모리 저장소 요구 사항에 중점을 둔다. 문제의 복잡도는 문제를 해결할 수 있는 최선의 알고리즘의 복잡도를 의미한다.
명시적으로 주어진 알고리즘의 복잡도를 연구하는 것을 알고리즘 분석이라고 하고, 문제의 복잡도를 연구하는 것을 계산 복잡도 이론이라고 한다. 알고리즘의 복잡도는 항상 이 알고리즘이 해결하는 문제의 복잡도의 상한선이므로 두 영역은 서로 밀접한 관련이 있다. 또한 효율적인 알고리즘을 설계하기 위해서는 특정 알고리즘의 복잡도와 해결하고자 하는 문제의 복잡도를 비교하는 것이 기본이 된다. 대부분의 경우 문제의 복잡도에 대해 알려진 유일한 내용이 가장 효율적인 알고리즘의 복잡도보다 낮다는 것 뿐이다. 따라서 알고리즘 분석과 복잡도 이론 사이에는 많은 부분이 겹친다.
알고리즘을 실행하는 데 필요한 자원의 양은 일반적으로 입력의 크기에 따라 달라지기 때문에 복잡도는 일반적으로 n → f(n) 함수로 표현되며, 여기서 n은 입력의 크기이고 f(n)은 최악 복잡도(n 크기의 모든 입력에 대해 필요한 자원의 최대값)이거나 평균 복잡도(n 크기의 모든 입력에 대한 자원의 평균값)이다. 시간 복잡도는 일반적으로 크기 n의 입력에 필요한 기본 연산의 수로 표현되며, 기본 연산은 주어진 컴퓨터에서는 일정한 시간이 걸리고 다른 컴퓨터에서 실행할 때는 상수배만큼만 변한다고 가정한다. 공간 복잡도는 일반적으로 n 크기의 입력에 대해 알고리즘이 필요로 하는 메모리 양으로 표현된다.