알고리즘의 시간 복잡도 분석

1. 도입

좀 더 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 알고리즘의 속도를 어떻게 측정할지를 정하는 것이다. 두 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것이다. 하지만 이 방법마저 여러가지 이유로 인해 정확하지는 않다. 그러므로 우리는 어떠한 기준이 필요하다.

반복문이 지배한다.

알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력을 많이 받게 되더라도 반복이 늘어나고, 출력을 많이 하는 것도 반복의 연속이다. 또한 탐색의 범위가 늘어나는 것도 반복이라고 생각할 수 있다. 알고리즘의 수행 시간은 매우 종류가 다양하지만 크게 몇 가지 분류로 나눌 수 있다.

2. 선형 시간 알고리즘

앞서 입력이 많아지면 시간도 늘어난다고 했다. 그리고 여기에 추가해서 알고리즘의 결과가 많은 입력값들을 중복으로 사용해서 도출해야한다면 어떻게 될까 아마 반복의 횟수가 폭발적으로 늘어날 것이다. 이를 개선하기 위해서는 어떻게든 반복의 횟수를 줄여하 할 것이고 이때 사용될 수 있는 방법이 중복된 계산을 없애는 것이다.
이렇게 개선된 알고리즘의 시간-속도 그래프가 일직선의 선형을 유지한다면 그것은 선형 시간(linear time) 알고리즘이 된다. 최소한 이 선형 시간 알고리즘이 가장 좋은 경우일때도 많다. 그 이유는 입력을 딱 한번 씩만 쳐다보고 해결되는 경우로 생각할 수 있기 때문이다.

3. 선형 이하 알고리즘

많은 데이터가 있다. 여기에서 단 하나의 특정 데이터를 찾아야 한다. 그렇다면 여러 방법이 있을 것이다. 처음부터 끝까지 돌면서 전체 탐색하는 방법이 가장 대표적일 것이다. 그렇다면 이 방법은 어떤가? 전체에서 절반만 나누어 데이터를 찾고, 만약 없다면 그 다음 절반, 또 그 다음 절반 이런식으로 범위를 좁혀가며 찾는 방식이다. 이런 방식을 사용하게 되면 확인해야 할 데이터의 수가 logN의 비율로 줄어들것이다. 다시 말해 엄청난 속도 향상이 있는 것이다. 이와 같이 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time) 알고리즘이라고 부른다.

이진 탐색

위에서 생각해본 알고리즘은 이진 탐색(binary search)라고 불린다. 이 알고리즘은 누구나 사전을 찾을 때, 혹은 전화번호를 뒤질 때 한 번쯤 이용했을 만한 간단한 아이디어이다. 하지만 굉장히 유용하게 사용되는 것도 사실이다. 이진 탐색 알고리즘은 다음과 같이 정의할 수 있다.

binsearch(A[],x)=오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때 A[i-1]<x<=A[i]인 i를 반환한다. 
이때 A[-1] = -무한대, A[N] = 무한대로 가정한다.

이것대로 만이라면 binsearch()의 입력을 만들기 위해서는 결국 모든 사진을 보면서 판단해야 한다. 그 전에 모든 입력을 정렬해야하는 문제도 있다. 그렇기 때문에 우리는 이 탐색 과정에서 선형 시간이 아닌가 하는 의문이 들 수 있다. 하지만 다음과 같은 이유 때문에 이 분석은 맞지 않다.

• A[]를 실제로 계산해서 갖고 있을 필요가 없다. 사실 이진 탐색 배열내부에서는 데이터중에 많은 부분을 탐색하지 않는다. 가운데 있는 것들에 대해서만 필요할 때 계산하면 된다.
• 데이터를 정렬해 두는 과정은 실제로 원하는 데이터를 찾는 것과는 별개이다.
  
  
  

4.지수 시간 알고리즘

다항 시간 알고리즘

반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들을 다항 시간 알고리즘이라고 부른다. 대다수의 알고리즘들은 다항 시간이 된다. 앞에서 언급한 선형 시간이나 선형 이하 시간과는 달리, 다항 시간이라는 하나의 분류에 포함되는 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있다. 보통 재귀함수를 사용하는 문제들에서 자주 볼 수 있다.

지수 시간 알고리즘

재귀를 사용하는 프로그램같은 것들을 만들면 어쩔 수 없이 모든 답을 한 번씩 다 확인하기 때문에, 전체 걸리는 시간은 만들 수 있는 답의 수에 비례하게 된다. N개의 케이스마다 Yes or No이기 때문에 결국 2^N가지의 답이 생기는 것이다. 만약 여기에 한번의 재귀당 반드시 호출하는 함수가 있고 이 함수의 동작시간이 M이라면 결국 수행 시간은 2^NM이다. 또한 이 함수를 수행할 때 반복문이 nm번이 수행된다면 전체 수행시간은 2^Nnm이 된다.
이 처럼 N이 하나 증가할 때마다 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작한다고 한다. 지수 시간이란 가장 큰 수행 시간 중 하나이다.
엄청나게 많은 시간이 걸리지만 아직도 더 효율적인 방법이 발견되지 않은 문제들이 넘쳐난다. 때문에 다항 시간 알고리즘이 이쓴ㄴ 문제는 계산적으로 쉬운 문제, 아직 없는 문제는 계산적으로 어려운 문제라고 한다.

소인수 분해의 수행 시간

입력으로 주어지는 숫자의 개수가 아니라 그 크기에 따라 수행 시간이 달라지는 알고리즘들 또한 지수 수행 시간을 가질 수 있다. 간단한 예시로는 소수를 소인수 분해하는 것이다. 어차피 1 이외의 약수는 존재하지 않기 때문에 일반적인 방법으로는 주어진 숫자보다 작은 수 모두를 반복시켜야 한다. 이런 불일치를 직관적으로 이해하기 위해 알고리즘의 수행 시간과 입력이 메모리에서 차지하는 공간의 관계를 생각해보자.
이전에 다룬 이진 탐색, 이동 평균 계산같은 알고리즘에서는 입력의 값들이 일정 범위 내에 있다고 가정할 수 있다. 그런 경우 입력의 개수와 메모리에서 차지하는 공간이 직접적으로 비례한다. 하지만 소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로, 숫자가 특정 범위 안에 있다고 가정할 수 없다. 입력의 값이 커지면 커질수록 숫자를 저장하는데 필요한 메모리의 공간도 증가한다. 이때 입력이 차지하는 비트의 수에 따라 수행 시간이 증가한다고 생각하면 이 불일치를 직관적으로 설명할 수 있다. 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가한다.이렇게 입력의 크기를 입력이 차지하는 비트 수로 정의하면 이 문제는 입력의 크기에 대해 지수 시간이 걸린다고 말할 수 있는 것이다.

5. 시간 복잡도

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

• 두 부호 있는 32비트 정수의 사칙연산
• 두 실수형 변수의 대소 비교
• 한 변수에 다른 변수 대입하기

반면에 다음과 같은 연산은 내부에 반복의 개념을 포함하기 때문에 기본적인 연산이 아니다.

• 정수 배열 정렬하기
• 두 문자열이 서로 같은지 확인하기
• 입력된 수 소인수 분해하기
  

시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이다. 물론 문제에서 해결할 입력의 크기가 매우 작을 경우 시간 복잡도는 큰 의미를 갖지 못할 수도 있다.

입력의 종류에 따른 수행 시간의 변화

입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다. 입력의 형태 역시 수행 시간에 영향을 미친다. 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 우리는 최선/최악의 경우, 그리고 평균적인 경웨 대한 수행 시간을 각각 따로 계산한다.

• 최선의 수행시간 : 한번만에 끝나는 경우 1.
• 최악의 수행시간 : 마지막까지 반복하는 경우 N.
• 평균적인 수행시간 : N/2.

점근적 시간 표기 : O 표기

시간 복잡도는 알고리즘의 수행 시간을 표기하는 방법이지만, 계산하기 너무 힘들다는 문제가 있다. 따라서 우리가 가장 깊이 중첩된 반복문만을 고려했던 것 처럼 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 된다. 이것을 더욱 간단하게 표현한 Big-O표기법이라는 것을 사용해 알고리즘의 수행 시간을 표기한다.
알고리즘의 입력의 크기가 두 개 이상의 변수로 표현될 때는 그중 가장 빨리 증가하는 항들만을 떼 놓고 나머지를 버린다. 예를 들어 길이가 각각 N과 M인 두 배열을 입력받는 함수가 있다고 가정하자. 이때 반복문의 수행 횟수는 N과 M을 갖는 식으로 표현할 수 있다.

시간 복잡도의 분할 상환 분석

알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것만으로만 결정하지는 않는다. 가끔은 문제의 조건에 따라 그보다 더 정확한 시간 복잡도를 계싼하는 것도 가능한데, 그 대표적인 예가 시간 복잡도의 분할 상환 분석(amortized analysis)을 사용하는 것이다. 예를 들어 각각의 동작 시간은 다르지만 반드시 전체 동작시간이 고정되어 있는 경우를 생각해보자. N가의 작은 작업들을 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 이런 방법을 적용할 수 있다. 이때 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다.
이런 개념은 괜히 복잡해 보이지만 종종 유용하다. 분할 상환 분석을 이요하면 일반적으로는 시간이 오래 결려 실행하지 못할 것이라고 여겼던 작업이 시간 안에 돌아가는 것을 이해할 수 있게 된다.

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

주먹구구식 법칙

정확한 동작시간을 추정하려면 모든 요소들에 대한 정보를 파악해야한다. 하지만 이것은 불가능에 가깝다. 그러므로 시간 복잡도와 입력 크기로 대략적인 값을 알고있어야한다. 프로그래밍 대회 참가자들이 많이 사용하는 법칙은 다음과 같다.

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

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

시간 복잡도는 알고리즘의 특성이지 문제의 특성이 아니다. 한 문제를 푸는 두 가지 이상의 알고리즘이 있을 수 있고, 이들의 시간 복잡도는 각각 다를 수 있기 때문이다. 이때 각문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문이 있는데 계산 복잡도 이론이 그것이다.