계산복잡도
오늘날 컴퓨터는 매초 수백만 개의 명령을 실행할 수 있지만, 알고리즘의 효율성은 여전히 중요하다. 예컨대 n(=2k)명의 학생에 대한 정보가 학번 순서로 정렬되어 있는 학적부 리스트에서 특정한 학번의 학생을 검색하는 업무를 생각해보자. 이 업무를 위한 알고리즘으로 순차 검색과 이진 검색 중 무엇을 선택하느냐는 효율성 측면에서 큰 차이를 낳는다.
순차 검색 알고리즘은 리스트의 첫 항목부터 차례로 목표값(찾고자 하는 학번)과 비교해 나가는 이해하기 쉬운 방법을 사용한다. 이 검색은 목표값에 따라 일찍 끝날 수도 늦게 끝날 수도 있지만, 최악의 경우 n개의 항목을, 평균적으로는 n/2개의 항목을 검사한 후에 종료될 것이다. 반면, 이진 검색 알고리즘은 리스트의 중앙 항목[n이 짝수면 n/2번째 항목, n이 홀수면 (n+1)/2번째 항목)]을 목표값과 비교하는 방식으로 진행된다. 그 항목이 목표값과 다르다면, 다음에는 목표값이 그 항목보다 큰지 작은지에 따라 그 항목의 우측 또는 좌측 리스트의 중앙 항목을 검사하기를 반복한다. 따라서 첫 단계에는 원래 길이(2k)의 리스트를, 두 번째 단계에는 원래의 반쪽 길이(2k-1)의 리스트를, 세 번째 단계에는 다시 그 반쪽 길이(2k-2)의 리스트를 검사하며, 최악의 경우 이 작업은 대략 k(=log2n)[1]번의 검사만에 완료된다. 만약 리스트의 항목 수가 30,000(≒215)개이고 하나의 항목을 검사하는 시간이 10밀리초[2]로 동일하다면, 순차 검색은 평균 15,000개 정도의 항목을 검사하여 150초에 끝나지만, 이진 검색은 최대 15개 정도의 항목을 검사하여 0.15초만에 끝난다.
알고리즘 수행에 걸리는 시간은 입력 자료의 항목 수 n에 대한 함수로 표현될 수 있는데, 그 함수는 컴퓨터의 성능에도 영향을 받는다. 그래서 n개의 항목으로 이루어진 자료를 처리하는 데 어떤 컴퓨터에서 n2초가 필요한 알고리즘이 다른 컴퓨터에서는 0.1n2초만에 수행될 수도 있다. 그러나 그 함수의 유형이 2차 다항식이라는 점은 바뀌지 않는다. 따라서 컴퓨터 이론에서는 그 함수의 유형을 통해 알고리즘의 효율성을 분류한다. 이러한 함수의 유형에는 계승식(n!)[3], 지수식, 2차 다항식, 1차 다항식, 로그식 등이 있으며, 이러한 유형을 그것의 대표식으로 간단히 표기하는 것을 빅-세타(θ) 표기법이라고 부른다. 이 표기법에서는 알고리즘 수행 시간이 2n초든 100n+100초든 모두 1차 다항식에 해당하므로 두 알고리즘의 효율성은 1차 다항식의 대표식인 n을 이용하여 θ(n)으로 표기되고, 각각 2n2+5n초와 8n2초가 걸리는 두 알고리즘의 효율성은 모두 θ(n2)으로 표기된다. 그렇다면 순차 검색 알고리즘은 θ(n), 이진 검색 알고리즘은 θ(log2n)에 속하며, θ(log2n)은 θ(n)보다, θ(n)은 θ(n2)보다 높은 효율성을 뜻한다. 이러한 알고리즘의 효율성은 알고리즘의 복잡도로 변환될 수 있는데, 이때 알고리즘의 복잡도가 높다는 것은 효율성이 낮다는 것을 의미한다.
문제의 복잡도는 그 문제를 위한 최선의 알고리즘의 복잡도로 정의된다. 물론 문제의 어떤 해법이 그 문제를 위한 최선의 알고리즘이라는 것을 파악하는 일은 매우 어렵다. 이러한 상황에서 어떤 문제의 복잡도에 대해 현재까지 알려진 사항을 표현하기 위해 빅-오(O) 표기법이 사용된다. 어떤 문제가 θ(f(n))에 속하는 알고리즘으로 해결되고, 현재까지는 그것이 최선의 해법이라면, 그 문제는 O(f(n))에 속한다고 말한다. 예컨대 순차적으로 정렬된 n개의 항목을 가진 리스트를 검색하는 문제에 대한 최선의 해법은 이진 검색으로 알려져 있으며, 따라서 이러한 검색 문제는 O(log2n)에 속한다.
n개의 입력 항목을 가진 문제가 n의 다항식으로 표현되는 시간, 이른바 다항 시간 이내에 해결 가능하다면, 그 문제를 다항식적 문제라 하며, 모든 다항식적 문제의 집합을 P로 나타낸다. 예컨대 검색 문제는 O(n)보다 복잡도가 낮으므로, 즉 n이 어느 이상으로 커지면 n의 1차 다항식으로 표현되는 시간 이내에 해결 가능하므로, P에 속한다. 특정한 문제가 P에 속하는지를 식별하는 것은 매우 중요한데, 이는 어떤 문제들이 실용적 해법을 갖는지에 관한 질문과 밀접하게 연관되어 있다. 예컨대 외판원 문제의 복잡도는 O(n!)로, 이 문제는 현재 P에 속하지 않는다. 이 문제는 자신의 도시에서 출발해 n개의 도시를 한 번씩 방문하여 다시 집으로 돌아오는 최단 경로를 찾는 문제이다. 이 문제에 대한 직관적인 해법은 모든 가능한 경로를 검사하는 것이다. 이 해법은 이해하기 쉬운 반면, n!이라는 너무 많은 경우의 수를 검사해야 하는 부담을 가진다. 예컨대 이 해법은 n=10이면 대략 360만 가지의 경우를, n=20이면 대략 200경 가지의 경우를 검사해야 한다. 결국 이 해법은 다항 시간을 초과하는 엄청나게 긴 시간이 걸리기에 현실적으로 수행 불가능하며, 컴퓨터의 속도 향상은 이 문제의 실용적 해결에 거의 기여하지 못한다. 그 대신 이 문제는 우연적 요소를 가미한 비결정론적인 알고리즘을 통해 다항 시간 내에 근사적으로 해결될 수 있으며, 실제로 이러한 해법들은 실용적으로 활용되고 있다. 이렇게 비결정론적인 알고리즘을 통해 다항 시간 내에 풀 수 있는 문제들의 집합을 NP라고 말한다. 이때 P는 NP의 부분집합이다.