[알고리즘 문제 해결 전략 #1] 4강 알고리즘의 시간 복잡도 분석
4.1 도입
알고리즘의 속도 측정은 보통 프로그램의 실행 시간으로 이야기 되지만, 기분이 되기에는 부적합하다. 왜냐하면 수행시간은 언어, 하드웨어, 운엉체제, 컴파일러 등 수많은 요소에 의해 바뀔 수 있기 때문이다.
1. 반복문이 지배한다.
알고리즘의 수행시간을 지배하는 것은 입력의 크기에 따라 수행되는 횟수가 정해지는 반복문이다.
4.2 선형 시간 알고리즘
1. 다이어트 현황 파악 : 이동 평균 계산하기
이동 평균(moving average)은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용 할 수 있다.
vector<double> movingAverage1(const vector<douvle>& 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;
}이와 같이 N 개의 데이터의 M 주기의 이동평균을 구하고 싶을때 M(N-M+1) 번 반복되는 코드가 작성된다.
하지만 연속되면서 반복되는 부분의 계산을 제거하기 위해서, M-1번째의 계산에서 0번째 값을 빼고 M 번째 값을 더함으로 M 번째 값을 구하는 방식으로 코드를 작성해 본다.
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; ++i){
partitalSum += A[i];
for(int i = M - 1; i < N; ++i){
partitalSum += A[i];
ret.push_back(partialSum / M);
partialSum -= A[i-M+1];
}
return ret;
}이로써 입력에 따라 선형적으로 수행시간이 증가하는 선형 알고리즘을 완성하였다.
4.3 선형 이하 시간 알고리즘
1. 이진 탐색
binsearch(A[]. x)= 오름차순으로 정렬된 배열 A[]와 찾고싶은 값 x 가 주어질 때 A[i-1] < x <= A[i] 인 i 를 반환한다.
이때 A[-1] = -INF , A[N] = INF 로 가정한다.
이러한 이진탐색은 순차로 내용을 확인하는 것이 아니라, 정렬된 배열에 중간 값을 확인하고 필요없는 부분을 배재함으로 검색하는 알고리즘이다.
2. 그래도 선형 시간 아닌가요?
N개의 사진이 있고, 찍은 순서대로 정렬되어 있다고 할때, 머리 염색한 이후 사진을 찾기 위해서는 모든 사진을 넘겨가며 머리 염색한 여부를 저장할 필요가 있을까?
첫번째로 A[]를 실제로 계산해서 갖고 있을 필요가 없다.
이진 탐색에서는 입력에 관해 몇개도 보지않는다. 따라서 미리 계산을 하기보다 i 가 주어질때 A[i]의 값을 직접 계산하는 하는 방법으로 간단히 문제 해결이 가능하다.
두번째로, 사진을 다운받고 정렬하는 과정은 실제로 염색전 후 사진을 찾는 것과는 별계의 문제이다.
따라서 이진 탐색은 선형 이하 시간 함수로 여긴다.
3. 구현
이진 탐색의 구현은 5.3 절에서 다시 살핍니다.
4.4 지수 시간 알고리즘
1. 다항 시간 알고리즘
N 과 N^2 , 그외 N의 거듭제곱의 선형 결합으로 이루어진 수행시간을 갖는 알고리즘을 다항 시간 알고리즘이라고 칭한다. 하지만 N^-100 도 다항 시간이기 때문에 다항시간간 시간 차이가 심할 수 있다.
2. 지수 시간 알고리즘
M가지의 음식을 만든다고 할때, 전체 만들 수 있는 음식 여부를 판단하는 방법은 2^M가지로 전체 수행에 엄청나게 영향을 미치는 큰 수이다. 이와같이 N이 증가할 때마다 시간이 배로 증가하는 알고리즘을 지수 시간에 동작한다고하고, 이것보다 빠른 알고리즘을 찾을 수 없는 문제가 전산학에 쌓이고 쌓였다.
보통 다항시간 알고리즘이 존재하면 쉬운문제, 아니면 어려운 문제라고 다룬다.
3. 소인수 분해의 수행 시간
소인수분해의 실행 횟수는 입력이 1개임에도 입력의 크기에 따라서 변화하는 특징이 있다. 이는 입력이 메모리에서 차지하는 공간과의 관계가 있다. 입력이 많아질수록 수행 시간이 커지는 직관과는 다르지만, 입력이 커지게 되면 메모리를 차지하는 비트 수가 증가하므로, 비트수가 증가할 때마다 최대 수행 시간이 두배 씩 늘어난다고 정의할 수 있어 지수 시간이 걸린다고 말할 수 있다.
4.5 시간 복잡도
시간 복잡도란 알고리즘의 수행시간을 기준으로, 알고리즘이 시행되는 동안 수행하는 기본적인 연산(두 부호있는 32비트 정수의 사칙연산, 두 실수형의 대소비교, 한 변수에 다른 변수 대입 등..)의 수를 입력의 크기에 대한 함수로 표현한 것이다.
시간 복잡도가 높다는 말은 입력의 크기가 증가할때 수행시간이 더빠르게 증가한다는 뜻이지, 입력의 크기가 충분히 작을 때에는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다.
1. 입력의 종류에 따른 수행 시간의 변화
입력의 크기만 수행시간을 변화시키는 것은 아니다.
int firstIndex(const vector<int>& array, int element){
for(int i = 0; i< array.size() ; ++i){
if(array[i] == element){
return i;
}
}
return -1;
}위와같이 배열의 원소를 찾아 인덱스를 반환하는 알고리즘의 경우, 입력의 종류에 따라 수행 시간이 달라집니다.
최선의 수행시간 : 1
최악의 수행시간 : N
평균적인 경우의 수행시간 : N / 2
3개의 기준 중 대개 최악의 수행시간과 평균적인 수행시간을 사용합니다.
2. 점근적 시간 표기: O(big O Notation)표기
전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하여 수행시간을 표기하는 방식이다. 간단하게 빨리 증가하는 항만 남긴 채 나머지를 다 버리는 표기법이다.
EX) N^2M + NM^2 = O(N^2M + NM^2), 42 = O(1)
3. O 표기법의 의미
O 표기법은 보통 함수의 상한을 나타낸다. f)N)이 주어질 때 , f(N) = O(g(N))이라고 쓰는것은 다음을 나타낸다.
아주 큰 N0 와 C (N0 , C > 0)을 적절히 선택하면 N0 <= N 인 모든 N에 대해 |f(N)| <= |C * g(N)| 이 참이 되도록 할 수 있다.
EX) f(N) = N^2 + 100N + 1 = O(N^2) 이라고 쓴다. 이때 N0 <=N 인 N에 대해서 N^2 + 100N + 1 <= C * N^2 을 구할 수 있다는 이야기 이다
4. 시간 복잡도 분석 연습
아래의 알고리즘의 시간 복잡도 O를 구해보기를 바란다.
void selectionSort(vector<int>& A){
for(int i = 0;i < A.size() ; ++i){
int minIndex = i;
for (int j = i+1; j<A.size();++j){
if(A[minIndex] > A[j])
minIndex = j;
swap(A[i], A[minIndex]);
}
}
void insertionSort(vector<int>& A){
for(int i = 0; i<A.size(); ++i){
int j = i;
while(j > 0 && A[j-1] > A[j]){
swap(A[j-1],A[j]);
--j;
}
}
}
5. 시간 복잡도의 분할 상환 분석
더 정확한 시간 복잡도를 계산하기 위해서 시간 복잡도의 분할 상환 분석(amortized analysis)를 사용하기도 한다.
예를 들면, N명이 N개의 라면을 끓여 남김없이 먹는다고 할때, 더 많인먹은 사람과 적게 먹는사람이 있겠지만, 각 사람이 평균 라면 1개를 먹었다고 여기는 방식이다. 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같게 여긴다는 뜻이다.
4.6 수행 시간 어림짐작하기
1. 주먹구구 법칙
대회의 시간 제한은 프로그램의 수행시간을 기준으로 하기때문에, 어느정도 입력의 최대 크기와 시간 복잡도를 보고 수행 시간을 어림 짐작할 수 있어야 한다. 하지만 동작 속도에 영향을 미치는건 입력과 시간 복잡도 외에도, CPU클럭속도, 클록당 명령어 수행개수, 메모리 접근패턴, 운영 체제와 컴파일러의 버전 등등 너무너무 많다.
그래도 대략적으로 짐작하는 것이 가능하다. 왜냐하면 위의 것들은 기껏해야 몇 배씩 차이나게 하지만, 시간 복잡도와 입력의 크기는 몇 천에서 몇 만배까지 빨라지거나 느려지게 할 수 있다.
입력의 최대 크기가 10000이고, 1초의 제한인 문제를 푼다고 할때, 보통 1초당 반복 수행 횟수를 1억을 넘어가면 시간 제한을 초과할 가능성이 있다고 이야기한다. 따라서 O(N^2)이하의 시간 복잡도를 가져야 한다고 하고, 그 이외의 요소들로 수행 속도를 열배 정도는 쉽게 바꿀 수 있기 때문에, 수행횟수가 기준의 10% 이하인 경우 이 법칙을 사용해야 한다.
2. 주먹구구 법칙은 주먹구구일 뿐이다.
- 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
O 표기 법으로 시간 복잡도를 표현할 때, 상수나 최고차항 이외의 항들을 전부 지워버리기 때문에, 실제 반복문의 수는 5배일 수도, 1/10 일수도 있다.
- 반복문의 내부가 복잡한 경우
내부가 단순하면 단순할수록 예측과 비슷해지고, 시간이 만ㅇ히 걸리는 연산을 많이 사용할 경우, 시간이 오래 걸릴 수밖에 없다.
- 메모리 사용 패턴이 복잡한 경우
현대의 CPU는 자주사용하는 데이터를 CACHE에 보관하여 처리하기 때문에, MISS가 자주발생하는 메모리 패턴일 경우 더 수행 속도가 느려질 수 있다.
- 언어와 컴파일러의 차이
- 구형 컴퓨터를 사용하는 경우
3. 실제 적용해 보기
이전에 다뤘던 최대 부분합을 찾는 알고리즘으로 수행시간이 어떻게 다른지 확인한다.
//O(N^3)
const int MIN = numeric_limits<int>::min();
int inefficientMaxSum(const vector<int>& A){
int N = A.size(), ret = MIN;
for (int i = 0;i<N;++i){
for(int j = i; j<N;j++){
int sum = 0;
for(int k = i; k<=j;++k)
sum += A[k];
ret = max(ret,sum);
}
}
return ret;
}
//O(N^2)
int betterMaxSum(const vector<int>& A){
int N = A.size(), ret = MIN;
for(int i = 0;i<N;++i){
int sum = 0;
for(int j = i;j<N;++j){
sum += A[j];
ret = max(ret,sum);
}
}
return ret;
}//O(nlgn)
int fastMaxSum(const vector<int>& A, int lo, int hi){
if(lo == hi)
return A[lo];
int mid = (lo + hi)/2;
int left = MIN, right = MIN, sum = 0;
for(int i = mid; i >= lo; --i){
sum += A[i];
left = max(left, sum);
}
sum = 0;
for(int j = mid + 1; j <= hi; ++j){
sum += A[j];
right = max(right,sum);
}
int single = max(fastMaxSum(A,lo,mid),fastMaxSum(A,mid+1,hi));
return max(left+right, single);
}//O(N)
int fastestMaxSum(const vector<int>& A){
int N = A.size(), ret = MIN, psum = 0;
for (int i = 0;i<N;++i){
psum = max(psum,0) + A[i];
ret = max(psum, ret);
}
return ret;
}위 4개의 다른 시간복잡도로
O(N^3) : 크기 2560인 입력 까지를 1초 안에 풀 수 있음
O(N^2) : 크기 40960인 입력까지를 1초안에 풀 수 있음.
O(NlgN) : 크기 대략 2천만인 입력 까지를 1초안에 풀 수 있음
O(N) : 크기 대략 1억 6천만인 입력까지를 1초안에 풀 수 있음
이는 간단한 반복문의 대략적인 수치이므로, 보수적으로 기준 시간을 정하는 것이 바람직하다.
4.7 계산 복잡도 클래스 : P , NP , NP-완비
대충 계산복잡도에 관한 이야기...
4.8 더 읽을거리
재귀 알고리즘의 시간복잡도를 구하는 방법으로 마스터 정리(MASTER THEOREM) 이란 것이 있다.