[02 알고리즘 분석] 4. 알고리즘의 시간 복잡도 분석

1. 도입

반복문이 지배한다.

여기 자동차 두 개가 있습니다. 서울에서 부산까지 서둘러 가야 하는데, 어느 쪽을 타고 가야 더 빨리 도착할 수 있을지를 알고 싶습니다. 다음은 두 자동차에 대한 정보입니다.

항목	자동차 A	자동차 B
시동 거는 데 걸리는 시간	3분	5초
문 열었다 닫는 데 걸리는 시간	1분	0초
운전석 등받이 조절에 걸리는 시간	5분	0초
앞 유리 닦는 데 걸리는 시간	4분	0초
최대 시속	200km/h	40km/h

 

네, 사실 자동차 B는 자전거입니다. 문이 없으니 문을 열었다 닫을 필요도 없고, 등받이가 없으니 등받이를 조절할 필요도 없지요. 하지만 그렇다고 해서 서울에서 부산까지 자전거를 타는 사람은 아마 별로 없을 겁니다. 자동차에서 더 오래 걸리는 항목들은 출발할 떄 한 번만 적용되는 반면, 최대 시속은 서울에서 부산까지 달리는 내내 적용되기 때문입니다. 서울에서 부산까지 달리는 데 30분쯤 걸린다면 시동 거는 데 걸리는 시간이 중요할 수 있지만, 그렇지 않기 때문에 앞 유리 닦는데 4분이 걸리건 5분이 걸리건 상관 없는 것입니다. 이렇게 한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다(dominate)고 표현합니다.

 

알고리즘 수행 시간을 지배하는 것은 무엇일까요? 바로 반복문입니다. 짧은 거리를 달릴 때는 자전거가 빠를 수 있는 것처럼 입력의 크기가 작을 때는 반복문 외의 다른 부분들이 갖는 비중이 클 수 있지만, 입력의 크기가 커지면 커질수록 반복문이 알고리즘의 수행 시간을 지배하게 됩니다. 따라서 대개 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정합니다. 이때 반복문의 수행횟수는 입력의 크기에 대한 함수로 표현합니다.

 

주어진 배열에서 가장 많이 등장하는 수를 찾는 코드가 있다고 해봅시다. 이 알고리즘의 수행 시간은 배열의 크기 N에 따라 변합니다. N번 수행되는 반복문이 두 개 겹쳐져 있으므로 반복문의 가장 안쪽은 항상 N² 번 실행되지요. 따라서 이 알고리즘의 수행시간은 N²입니다.

 

그런데 입력으로 주어지는 숫자들이 사실 100점 만점으로 주어지는 중간 고사 점수였다고 합시다. 이처럼 숫자의 법위가 작다면 배열을 이용해 각 숫자가 등장하는 횟수를 쉽게 셀 수 있습니다. 그리고 마지막에 빈도수 배열을 순회하면서 최대치의 위치를 찾으면 되지요. 이 구현에는 반복문이 두 개 있습니다. 하나는 N번 수행되고, 다른 하나는 100번 수행되므로 전체 반복문의 수행 횟수는 N+100이 됩니다. 그런데 N이 커지면 커질수록 사실 후자의 반복문은 수행 시간에서 차지하는 비중이 줄어들게 됩니다. 따라서 궁극적으로는 이 알고리즘의 수행 시간은 N이라고 씁니다.

 

2. 선형 시간 알고리즘

 

다이어트 현황 파악: 이동 평균 계산하기

이동 평균(moving average)은 주식의 가격, 연간 국내 총생산(GDP), 여자친구의 몸무게 등 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준입니다. 시간에 따라 관찰된 숫자들이 주어질 때 M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의됩니다. 따라서 새 관찰 값이 나오면 M-이동 평균은 새 관찰 값을 포함하도록 바뀝니다.

 

N개의 측정치가 주어질 때 매달 M달 건의 이동 평균을 계산하는 프로그램을 짜면 다음과 같습니다.

vector<double> movingAverage1(const vector<double>& A, int M) {
    vector<double> ret;
    int N = A.size();
    for(int i = M-1; i < N; ++i) {
        double partialSum = 0
        for(int j = 0; j < M; ++j) {
            partialSum += A[i-j];
        }
        ret.push_back(partialSum / M);
    }
    return ret;
}

 

이 코드의 수행시간은 for문에 지배됩니다. j를 사용하는 반복문은 항상 M번 실행되고 i를 사용하는 반복문은 N - M + 1번 실행되니, 전체 반복문은 M x (N - M + 1) = N*M - M^2 + M번 반복됩니다. N = 12, M = 3 이면 반복 횟수는 30번이 됩니다.

 

그런데 위 프로그램을 좀 더 빠르게 만들 수는 없을까요? 여기에서 중요한 아이디어는 중복된 계산을 없애는 것입니다. 측정치가 M개는 되어야 이동평균을 계산할수 있으니 태어난 이후 M-1일부터 이동 평균을 계산할 수 있습니다. 이때 M-1일의 이동 평균과 M일의 이동 평균에 포함되는 숫자들을 보면 0일과 M일의 몸무게를 제외하면 전부 겹친다는 것을 알 수 있습니다. 그러면 측정한 몸무게의 합을 일일이 구할 필요 없이 M-1일에 구했던 몸무게의 합에서 0일째에 측정한 몸무게를 빼고 M일째에 측정한 몸무게를 더하면 어떨까요?

 

이 아이디어를 구현하면 다음과 같은 코드가 됩니다. 하나로 묶여있던 두 개의 반복문이 분리되었습니다. 따라서 이 프로그램의 반복문 수행 횟수는 M - 1 + (N - M + 1) = N 이 됩니다. 이제 N값이 커져도 두렵지 않습니다.

vector<double> movingAverage2(const vector<double>& A, int M) {
  vector<double> ret;
  int N = A.size();
  double partialSum = 0;
  for(int i=0;i<M-1;++i) {
      partialSum += A[i];
  }
  for(int i=M-1;i<N;++i) {
      partialSum += A[i];
      ret.push_back(partialSum / M);
      partialSum -= A[i-M+1];
  }
  return ret;
}

 

위 프로그램의 수행시간은 N에 정비례합니다. N이 두 배 커지면 실행도 두 배 오래걸리고, 반으로 줄어들면 수행 시간도 반으로 줄어듭니다. 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 되지요. 때문에 이런 알고리즘을 선형 시간(linear time) 알고리즘이라고 부릅니다. 선형 시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많습니다. 주어진 입력을 최소한 한 번씩 쳐다보기라도 하려면 선형시간이 걸릴 수 밖에 없으니까요.

 

3. 선형 이하 시간 알고리즘

 

어떤 문제건 입력된 자료를 모두 한 번 훑어보는 데에는 입력의 크기에 비례하는 시간, 즉 선형 시간이 걸립니다. 그럼 선형 시간보다 빠르게 동작하는 알고리즘들은 입력된 자료를 다 보지도 않는단 말인데, 과연 이런 알고리즘이 어떻게 존재할 수 있을까요? 입력으로 주어진 자료에 대해 우리가 미리 알고 있는 지식을 활용할 수 있다면 이런 일이 가능합니다.

 

구체적인 예를 들어보겠습니다. 발라드 그룹 멤버 A군의 코 성형 전 고등학교 사진이 공개되었다고 합시다. 남들 몰래 A군의 팬인 저는 A군이 대체 언제 성형을 했는지 알고 싶어서 검색엔진으로 A군의 사진 십만장을 찾아서 이들을 촬영 날짜 순으로 정렬했습니다. 그럼 A군이 언제 성형했는지를 가능한한 정확하게 알려면 대체 몇 장의 사진을 확인해야 할까요?

 

가장 좋은 방법은 남은 사진들을 항상 절반으로 나눠서 가운데 있는 사진을 보는 것입니다. 우선 가운데 있는 5만번째 사진을 확인해봅니다. 만약 이 사진에서는 코를 성형하지 않은 상태라면 이 전의 사진은 볼 필요가 없습니다. 따라서 우리가 확인해야 할 사진은 뒤의 5만장으로 줄어들었습니다. 그중 가운데 있는 7만 5천번째 사진을 확인하면 이제 확인해야 할 장수는 2만 5천장으로 줄어듭니다. 확인할 때마다 남은 장수가 대략 절반으로 줄어든다고 하면 전부 몇장의 사진을 확인해야 할까요?

확인한 사진의 수	0	1	2	...	12	13	14	15	16
남은 사진	100,000	50,000	25,000	...	24	12	6	3	1

 

대략 열일곱 장의 사진만 확인하면 성형한 시점을 찾아낼 수 있습니다. 이때 봐야하는 사진의 장수를 N에 대해 표현하면 어떻게 될까요? N을 계속 절반으로 나눠서 1 이하가 될 때까지 몇 번이나 나눠야 하는지로 알 수 있는데 이것을 나타내는 함수가 바로 로그입니다. 매번 절반씩 나누니 밑이 2인 로그가 됩니다. 이를 줄여서 lg로 쓰겠습니다. 따라서 확인해야 하는 사진의 장수는 대략 lgN이라고 할 수 있습니다.

 

lg는 굉장히 느리게 증가하는 함수입니다. 만약 지구에서 달까지 닿도록 A군의 사진을 1.5조 장을 쌓아 놓더라도 이 중에서 원하는 성형전 사진을 마흔장만 보고 찾아낼 수 있지요. 이와 같이 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time) 알고리즘이라고 부릅니다.

 

4. 지수 시간 알고리즘

 

다항 시간 알고리즘

변수 N과 N^2, 그 외 N의 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부릅니다. 반복문의 수행 횟수를 입력 크기의 다향식으로 표현할 수 있는 알고리즘들을 다항 시간 알고리즘이라고 부릅니다. N이나 N^2도 다항시간이지만, N^6도, N^42도 심지어는 N^100 도 다항시간입니다.

 

지수 시간 알고리즘

2^N 과 같은 지수 함수는 알고리즘 전체 수행 시간에 엄청난 영향을 미칩니다. N개의 선택에 대해서 예, 아니오 두 선택지가 있을 때 가능한 모든 경우의 수는 2^N 이 됩니다. 이와 같이 N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작한다고 말합니다. 지수 시간은 가장 큰 수행 시간 중 하나로, 입력의 크기게 따라 다항 시간과는 비교도 안되게 빠르게 증가합니다.

 

그런데 이 알고리즘이 이렇게 오래 걸리는 이유는 어디까지나 이 알고리즘이 무식하기 때문이겠죠? 이것보다 훨씬 빠른 알고리즘이 있겠죠? 아닙니다. 지수시간보다 빠른 알고리즘을 찾지 못한 문제들이 전산학에는 쌓이고 쌓였습니다. 이처럼 아직 지수 시간보다 빠른 알고리즘을 찾아내지 못한 문제들이 아주 많기 때문에 다항 시간과 지수 시간 사이의 경계는 현재의 전산학에서 효율적으로 해결할 수 있는 문제와 효율적으로 해결하는 방법을 아직 찾아내지 못한 문제의 경계 역할을 하고 있습니다. 

 

5. 시간 복잡도

 

시간 복잡도는 가장 널리 사용되는 알고리즘의 수행시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이라고 생각하면 됩니다.

 

입력의 종류에 따라 수행시간이 달라지는 것을 고려하기 위해 우리는 최선/최악의 경우, 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산합니다.

점근적 시간 표기: O 표기

우리가 가장 깊이 중첩된 반복문만을 고려했던 것처럼 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 됩니다. 여기에서 한 반짝 더 나아가서 많은 사람들은 이것을 더욱 간단하게 표현한 대문자 O 표기법(Big-O Notation)이라는 것을 사용해 알고리즘의 수행 시간을 표현합니다. O 표기법은 간단하게 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법입니다.

 

예를 들어 어떤 알고리즘 수행 시간이 5/3N^2 - NlgN/2 + 16N - 7 이라고 합시다. 여기에는 네 개의 항이 있는데 N이 증가할 때 가장 빨리 증가하는 항은 5/3N^2 이고, 여기에서 상수를 떼어내면 N^2이 되지요. 그러면 우리는 이 알고리즘의 수행 시간을 O(N^2)이라고 씁니다. 

 

알고리즘의 입력의 크기가 두 개 이상의 변수로 표현될 때는 그중 가장 빨리 증가하는 항들만을 떼 놓고 나머지를 버립니다.

 

그리고 N^2M +NlgM + NM^2 의 경우는 N^2M과 NM^2 중 어느 한쪽이 빠르게 증가한다고 할 수 없기 때문에 둘 다 O 표기에 포함됩니다. O(N^2M + NM^2) 가 됩니다. 

 

O 표기법이 수행 시간의 상한을 나타낸다는 사실을 통해 알고리즘의 최악의 수행 시간을 알아냈다고 착각하는 일이 흔히 있습니다. 하지만 O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있는 것은 아닙니다.

 

6. 수행 시간 어림짐작하기

 

프로그래밍 대회 참가자들이 사용하는 주먹구구 법칙은 다음과 같습니다.

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.

 

이 기준을 이용해 앞의 경우 입력의 최대 크기 N이 10000인 경우 시간 안에 실행할 수 있을지 판단해 봅시다. O(N^3) 알고리즘과 O(NlgN) 알고리즘은 쉽게 판단할 수 있습니다. N^3에 10000을 대입하면 1억을 훨씬 초과하고, NlgN에 10000을 대입하면 1억에 훨씬 미치지 못하기 때문이다.

 

하지만 주먹구구 법칙은 주먹구구일 뿐입니다. 절대로 맹신해서는 안됩니다. 이 기준보다 느리지만 시간 안에 수행되는 프로그램이 얼마든지 있을 수 있고, 가끔은 이 기준보다 빠르지만 시간 안에 수행되지 않는 프로그램도 있기 때문입니다. 

 

7. 계산 복잡도 클래스: P, NP, NP-완비

 

시간 복잡도는 알고리즘의 특성이지 문제의 특성이 아닙니다. 한 문제를 푸는 두 가지 이상의 알고리즘이 있을 수 있고, 이들의 시간 복잡도는 각각 다를 수 있기 때문입니다. 이때 각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문이 있습니다. 이론 컴퓨터 과학의 중요한 분야인 계산 복잡도 이론이 그것이지요. 몇몇 중요한 개념을 짚고 넘어가 봅시다. 

문제의 특성 공부하기

계산 복잡도 이론은 각 문제의 특성을 공부하는 학문입니다. 다음 두 가지 문제를 비교해봅니다.

• 정렬 문제 : 주어진 N개의 정수를 정렬한 결과는 무엇인가?
• 부분 집합의 합 문제 : N개의 수가 있을 때 이 중 몇 개를 골라내서 그들의 합이 S가 되도록 할 수 있는가?

이 두 문제 중 어느 것이 더 쉽거나 더 어려운지 분간할 수 있을까요? 단 이떄 정의하는 문제의 '어려움'은 우리가 문제를 풀 때의 난이도가 아닙니다. 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타냅니다. 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 빠른 알고리즘이 없는 문제는 계산적으로 어렵다고 말하지요. 알고리즘을 유도하는 과정이 책 열 권이고 그 구현이 천만 줄이라도, 수행 시간만 빠르다면 그 문제는 쉬운 문제입니다. 그럼 빠른 알고리즘의 기준은 대체 무엇일까요? 일반적으로 우리는 다항 시간 알고리즘이나 그보다 더 빠른 알고리즘들만을 '빠르다'고 말합니다.

 

계산 복잡도 이론에서는 이렇게 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 합니다. 예를 들어 정렬 문제에는 다항 시간 알고리즘이 수없이 많이 존재하므로, 정렬 문제는 P문제입니다. P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스(complexity class)라고 부릅니다. 엄청나게 다양하고 많은 복잡도 클래스가 있지만, 그중 두 가지의 클래스가 가장 중요합니다. 바로 P 문제와 NP 문제입니다.

난이도의 함정

P가 다항 시간에 풀 수 있는 문제면, 그 짝인 NP는 당연히 풀 수 없는 문제여야 하는데 왜 이렇게 비직관적으로 만들었는가 항의하고 싶을 겁니다. 이때 주목할 부분은 어떤 문제를 다항 시간에 풀 수 있음을 증명하기란 쉽지만, 풀 수 없음을 보이기란 어렵다는 점입니다. 흔히 말하는 UFO의 존재 논쟁과 비슷합니다. UFO가 존재함을 증명하려면 UFO 하나만 가져오면 되지만, 존재하지 않음을 증명하려면 전 우주를 다 뒤져야 합니다. 

 

이처럼 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기란 어렵습니다. 계산 복잡도에서 흔히 말하는 '어려운 문제'들은 다음과 같이 정의됩니다.

• 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼습니다.
• 그리고 앞으로는 기준 문제만큼 어렵거나 그보다 어려운 문제들, 다시 말해 '기준 이상으로 어려운 문제들'만을 어렵다고 부릅니다.

계산 복잡도 이론에서는 두 문제 사이의 계산 난이도 비교를 위해 환산(reduction)이라는 기법을 이용합니다. 환산이란 한 문제를 다른 문제로 바꿔서 푸는 기법입니다. B 문제의 입력을 적절히 변형해 A 문제의 입력으로 바꾸는 환산 알고리즘이 존재한다고 합시다. 이때 A를 푸는 가장 빠른 알고리즘을 가져오면, 이것을 환산 알고리즘과 결합해 B를 푸는 알고리즘을 만들 수 있습니다. 환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 겂니다. B를 푸는 가장 빠른 알고리즘은 앞에서 결합된 알고리즘과 같거나 더 빠를 테니, (B 문제를 푸는 가장 빠른 알고리즘은 최소한 'A + 환산 알고리즘' 과 같은 시간이 걸리고, 아직 밝혀지지는 않았지만 더 빠르게 B문제를 푸는 알고리즘이 존재할 수 있음) 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없습니다.

 

A ≒ (A + 환산 알고리즘) = B

 

앞에서 정의한 대로, 이 경우 A가 B 이상으로 어렵다는 것을 알게 되지요. 간단한 예로 주어진 배열을 비교 정렬하는 문제와 최소치를 찾는 문제의 난이도를 비교해 봅시다. 주어진 배열을 다항 시간에 정렬하고 첫 번째 값을 취하면 최소치를 쉽게 얻을 수 있습니다. 따라서 최소치를 구하는 데 걸리는 시간이 정렬보다 오래 걸릴 수는 없지요. 그래서 정렬 문제는 최소치 문제 이상으로 어렵다고 말할 수 있습니다.

NP 문제, NP 난해 문제

이제 문제들의 난이도를 비교할 수 있으니 어려운 문제의 기준을 정해봅니다. 이 기준을 정하기 또한 쉽지 않은데요. 이 때 어려운 문제의 기준이 되는 것이 바로 SAT 문제(satisfiability problem) 입니다. SAT 문제란 N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수값들의 조합을 찾는 문제입니다. 예를 들어 불린 값 변수 a, b, c로 구성된 다음 논리식은 세 변수의 값이 특정 조합을 이루어야 만족됩니다.

((a||b||!c)&&(!c||!a)&&((!a&&b)||(b&&!c)))&&(!b||(!a&&!c))

 

이 문제가 대체 뭐길래 어려운 문제의 기준으로 삼는 걸까요? SAT 문제에는 아주 중요한 의미가 있습니다. 바로 SAT 문제는 모든 NP 문제 이상으로 어렵다는 것입니다.

 

NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 말합니다. 예를 들어 부분 집합 합 문제는 NP 문제입니다. 부분 집합 합 문제의 답이 주어졌을 때 이것이 원래 집합의 부분 집합인지, 그리고 원소들의 합이 S인지 다항 시간에 쉽게 확인할 수 있기 때문입니다. 또한 모든 P 문제들은 모두 NP 문제에도 포함됩니다. NP 문제들은 중요하고, 유명하고, 우리가 관심있는 수많은 문제들을 엄청나게 많이 포함합니다. SAT가 모든 NP 문제 이상으로 어렵다는 말은 SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다는 얘기입니다. 이런 속성을 갖는 문제들의 집합을 NP-난해(NP-Hard) 문제라고 부릅니다. NP-난해 문제들은 그 이름처럼 아주 어려워서, 아직 아무도 NP-난해 문제를 다항 시간에 푸는 방법을 발견하지 못했습니다. 계산 복잡도 이론에서 어렵다고 부르려면 이 정도쯤은 되어야 합니다.

 

NP-난해 문제이면서 NP인 문제들을 NP-완비(NP-Complete) 문제라고 합니다. NP-완비 문제는 생각보다 자주 만날 수 있습니다. 부분 집합 합 문제도 NP-완비 문제 중 하나죠.

P=NP?

밀레니엄 7대 수학 난제로 유명해진 P=NP 문제는 P와 NP가 같은지를 확인하는 문제입니다. NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있습니다. 이 경우 NP에 속한 모든 문제를 다항 시간에 해결할 수 있으므로 P=NP 임을 알 수 있겠지요. 그 반대로 NP 문제 중 하나를 골라 P에 포함되어 있지 않음을, 다시 말해 다항 시간에 푸는 방법이 없음을 증명하면 P != NP 임을 보일 수 있습니다. 이 문제가 아직까지 미해결이라는 말은 둘 중 하나에 성공한 사람이 아직 아무도 없다는 이야기입니다.

---

P와 NP 문제에 대해서는 아래 영상을 통해서 자세하게 확인할 수 있다.

 

https://youtu.be/nxbufH4JnpA?si=-eelaNoSp9pu3MP3

 

P 문제란?
결정론적 튜링 기계를 사용해 다항시간 내에 답을 구할 수 있는 문제
대표적인 예로는 거품정렬이 있는데, n개의 정수 입력값이 있고, 두 수를 비교하는 데 1초가 걸린다고 할 때 계산에 드는 총 시간은 ((n-1) * n ) / 2 만큼 걸린다. 이렇게 n에 대한 2차식으로 즉, 다항시간으로 표현이 가능하므로 거품정렬은 P문제라고 할 수 있다.

 

NP 문제란?
비결정론적 튜링 기계(여러 개의 선택지)를 사용해 다항시간 내에 답을 구할 수 있는 문제
대표적인 예로는 부분집합의 합이 있다. {-2, 10, 6, -5, -3} 이라는 집합이 있을 때 부분집합의 합이 0이 되는 부분집합이 있는지 물어보는 문제가 있다고해보자. 정답은 Yes이다. {-2, 10, -5, -3} 으로 뽑으면 부분집합의 합이 0이 되기때문이다. 이때 운이 좋아서 -2, 10, -5, -3 을 차례대로 뽑았다고 하면 이때 걸리는 시간은 (n - 1) 에 해당하고 이는 다항시간이다. 그런데 문제는 이 숫자조합을 찾아내는 것이다. 
만약, n 개의 원소를 갖는 집합에 대해서 결정론적 튜링기계를 사용한다면 부분집합의 개수인 2^n 만큼 연산을 해야할 것이다. 즉 다항시간이 걸리는 것이 아니라 지수시간이 소요된다. 입력의 크기가 커지면 커질수록 소요되는 시간이 기하급수적으로 늘어나게 된다.