[종만북] 04. 알고리즘의 시간 복잡도 분석 (1)

04. 알고리즘의 시간 복잡도 분석 (1)

4.1 도입 4.2 선형 시간 알고리즘

알고리즘의 속도를 어떻게 측정할 것인가. 결국은 반복문이 지배한다. 대개 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다. 

M 개 의 이동 평균을 구하는 알고리즘을 알아보자. (vecotr 관련 글)

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;
}

첫번째 반복문이 N-M+1 번 두번째 반복문이 M 번 실행되므로 $$MN-M^2+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-1; i++) // 이동평균 구하는 개수 M 직전까지 더해둔다.
    	partialSum += A[i];
    for(int i = M-1; i < N; i++){
    	partialSum += A[i]; // M까지 더해준다.
        ret.push_back(partialSum / M); // 실제 이동평균을 구해서 ret 에 넣는다.
        partialSum -= A[i-M+1]; // 이전 구간의 첫번째 값을 빼준다.
    }
    return ret;
}

더 빠른 프로그램을 위한 새로운 알고리즘에서는 M-1 번 + N-M+1 번 실행되므로 총 N 번 반복된다!

입력에 대비해 걸리는 시간을 그려보면 정확히 직선이 될것이다. 이를 선형 시간 (linear time) 알고리즘 이라고 부른다. 이와 같은 선형 시간 알고리즘은 대개 우리가 찾을 수 있는 가장 좋은 알고리즘인 경우가 많다.

---

4.3 선형 이하 시간 알고리즘

 선형 시간보다 빠르게 동작하는 알고리즘들은 입력된 자료를 다 보지도 않는단 말이다. 이는 입력으로 주어진 자료에 대해 우리가 미리 알고 있는 지식을 활용할 수 있다면 가능하다.

어떤 연예인이 성형을 한 시점을 알기 위해 10만장의 사진을 정렬해 두었다면 어떻게 하는 것이 효율적일까? 모든 것을 뒤져보기 보다는 50,000 번째 사진을 보고 아니라면 그 이전 사진들을 보고, 또 그것의 반 25,000 번째 사진을 보고 아니라면 그 이전 사진들을 보고, 그것의 반 ... 으로 한 번 확인시마다 절반이 된다. 그러므로, 확인해야 하는 사진의 장수는 대략 $$lg N$$ 이라고 할 수 있다. 선형 이하 시간(sublinear time) 알고리즘 이라고 부른다.

이진 탐색

위의 예시를 이진 탐색이라고 부르며 이 책에 실린 모든 알고리즘 중 가장 유용하게 쓰이는 것 중 하나 일 것이다.

하지만, 간단한 아이디어와는 달리 이진 탐색을 정확하게 구현하기는 매우 까다롭다. 5.2 절에서 다시 다루겠다.

---

4.4 지수 시간 알고리즘

다항 시간 알고리즘

 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부르며, 반복문의 수행 횟수를 이렇게 표현할 수 있는 알고리즘들을 다항 시간 알고리즘 이라고 부른다. 거듭제곱이 2이든 5이든 100이든 모두 다항 시간 알고리즘이기 때문에 해당 알고리즘이 다항 시간 알고리즘이라 하여도 빠르다는 것을 보장할 수는 없다. 하지만, 다항 시간보다 훨씬 더 많은 시간이 걸리는 알고리즘들이 있기 때문에 구분지어 명명한 것이다.

지수 시간 알고리즘

 N 이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간 (exponential time) 에 동작한다고 한다. 이 알고리즘이 무식하다고 생각할 수 있지만 지수 시간보다 빠른 알고리즘을 찾지 못한 문제들이 전산학에는 매우 많다. 다항 시간 알고리즘이 있는 문제는 계산적으로 쉬운 문제, 아직 없는 문제는 계산적으로 어려운 문제라고 이야기 한다. (4.7절) 11장에서는 지수 시간 알고리즘을 좀 더 효율적으로 바꿀 수 있는 방법을 소개한다.

소인수 분해의 수행 시간

 입력으로 주어지는 숫자의 개수가 아니라 그 크기에 따라 수행 시간이 달라지는 알고리즘들 또한 지수 수행 시간을 가질 수 있다.

// 자연수 n 의 소인수 분해 결과를 담은 정수 배열을 반환.
vector<int> factor(int n) {
	if(n == 1) return vector<int>(1,1); // 기저 사례 n = 1 일때
    vector<int> ret;
    for(int div = 2; n > 1; div++)
    	while(n % div == 0) {
        	n /= div;
            ret.push_back(div);
        }
    return ret;
}

이 코드는 N의 크기에 따라 반복문의 수행 횟수가 달라지게 된다. 최악의 경우인 N이 소수인 경우일 때, 반복문의 실행 횟수는 N-1 이 되기 때문에 이 함수가 선형 시간이 걸린다고 생각하기 쉽다.

하지만, 알고리즘의 수행 시간과 입력이 메모리에서 차지하는 공간의 관계를 생각해보자. 입력 값인 n 은 값에 제한이 없기에, 입력의 값이 커질수록 숫자를 저장하는데 필요한 메모리의 공간도 증가한다. 비트의 수에 따라 수행 시간이 증가한다고 생각하면 의문을 해결할 수 있다. 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가한다. 그러므로, 지수 시간이 걸린다.