선형 이하 시간 알고리즘

어던 문제건 입력된 자료를 모두 한 번 훝어보는 데에는 입력의 크기에 비례하는 시간, 즉 선형 시간이 걸린다. 그럼 선형 시간보다 빠르게 동작하는 알고리즘들은 입력된 자료를 다 보지도 않는단 말이다. 입력으로 주어진 자료에 대해 우리가 미리 알고 있는 지식을 활용할 수 있다면 이런 일이 가능하다.
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time)알고리즘이라고 부른다.

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

int binarySearch(int A[], int low, int high, int target) {
	while (low <= high) {
    		int mid = (low + high) / 2;
            if (A[mid] == target) 
            	return (mid);
            if (A[mid] > target) 
            	high = mid - 1;
            else 
            	low = mid + 1;
    	}
        return (-1);
}

int binarySearchRecur(int A[], int low, int high, int target) {
	if (low > high)
    		return (-1);
    	int mid = (low + high) / 2;
        if (A[mid] == target)
        	return (mid);
        if (A[mid] > target) {
        	return (binarySearchRecur(A, low, mid - 1, target));
        }
        return (binarySearchRecur(A, mid + 1, high, target))
}

int metaBinarySearch(int A[], int low, int high, int target) {
	int bin = 1, idx = 0;
    	while (bin <= high)
        	bin <<= 1;
        for (bin >>= 1;; bin >>= 1){
        	int i = idx + bin;
            if (i <= high && A[i] <= target) {
            	if (A[i] == target)
                	return (i);
                idx = i;
            }
            if (bin == 0)
            	break;
        }
}

지수 시간 알고리즘

다항시간 알고리즘

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

지수 시간 알고리즘

N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작한다고 말한다.

소인수 분해의 수행 시간

소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미친다.
입력의 값이 커지면 커질수록 숫자를 저장하는데 필요한 메모리의 공간도 증가한다. 이때 입력이 차지하는 비트의 수에따라 수행 시간이 증가한다고 생각하면된다. 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가한다.

시간 복잡도

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

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

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

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

가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 때문에, 이것이 시간 복잡도의 대략적인 기준이 된다.
시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이다. 이 말에 숨어 있는 의미는 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니라는 것이다. 입력의 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다. 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 효율적이 된다.
예를 들어 같은 일을 하는 두 개의 알고리즘 A와 B가 있는데 입력의 크기 N에 대해 A는 10240 + 35 logN, B는 2N^2의 시간이 걸린다고 하자. A는 선형 시간 이하 알고리즘이고, B는 다항 시간 알고리즘의 예시이다. 아래의 그래프는 두 알고리즘의 수행 시간이 입력의 크기가 변함에 따라 어떻게 변하는지 보여준다. 알고리즘 A의 속도는 입력의 크기가 증가해도 거의 변하지 않기 때문에, 전체적인 맥락에서는 알고리즘 B보다 더 바른 알고리즘이라고 할 수 있다. 그러나 N = 10일 경우에는 알고리즘 B가 훨씬 빠르다. 알고리즘 A는 입력의 크기가 작더라도 더 빨라지지 않기 때문이다. 이런 의미에서 시간 복잡도는 완전한 속도의 기준은 아니다. 문제에서 해결할 입력의 크기가 매우 작을 경우 시간 복잡도는 큰 의미를 갖지 못할 수도 있다.

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

입력의 크기뿐만 아니라 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다. 예를 들어 배열에서 주어진 숫자를 찾아서 그 위치를 반환하는 함수를 코드로 구현했다고 하자.

// array[i] = element인 첫 i를 반환한다. 없으면 -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이 된다.

  • 평균적인 경우의 수행 시간
    평균적인 경우의 수행 시간을 분석하기 위해서는 존재할 수 있는 모든 입력의 등장 확률이 모두 같다고 가정한다. 만약 주어진 배열이 항상 찾는 원소를 포함한다고 가정하면 반환 값의 기대치는 대략 N/2이고, 평균적인 수행 횟수는 N/2이 된다.

점근적 시간 표기: O표기

시간 복잡도는 알고리즘의 수행 시간을 표기하는 방법이지만, 계산하기 힘들다는 문제가 있다. 우선 알고리즘이 실행될 때 필요한 명령어의 수라는 것이 모하하고, 알고리즘이 복잡할 때 그걸 한 줄 한 줄 세고 있는 것도 비효율적이다. 따라서 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 된다.
여기에서 이것을 더 간단하게 표현한 대문자 O표기법(Big-O Notation)이라는 것을 사용해 알고리즘의 수행 시간을 표기한다. O 표기법은 간단하게 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다.
예를 들어 어떤 알고리즘의 수행 시간이 f(N) = 200N^2 - Nlog(N/2) + 10N - 7이라고 하자. 여기에는 네 개의 항이 있는데 N이 증가할 때 가장 빨리 증가하는 항은 200N^2이고, 여기에서 상수를 떼어내면 N^2이 된다. 그러면 이 알고리즘의 수행 시간을 O(N^2)이라고 쓴다.
알고리즘의 입력의 크기가 두 개 이상의 변수로 표현될 때는 그 중 가장 빨리 증가하는 항들만을 떼 놓고 나머지를 버린다.
예를 들어 길이가 각각 N과 M인 두 배열을 입력받는 함수가 있다고 가정하자. 이때 반복문의 수행 횟수는 N과 M을 갖는 식으로 표현할 수 있다. 다음은 몇 가지 알고리즘의 수행 횟수와 이들의 O표기를 보여준다.

  • (2^N) M = O((2^N)M)
  • 64N^2 M + 64NM = O(N^2 M)
  • N^2 M + NlogM + N M^2 = O(N^2 M + N M^2)
  • 42 = O(1)

마지막에서 두번째 예는 N^2 * M과 N * M^2 어느 한쪽이 빠르게 증가한다고 할 수 없기 때문에 둘 다 O표기에 포함된다. 마지막 예에서는 알고리즘이 입력의 크기와 상관없이 항상 같은 시간이 걸린다. 이때 대문자 O표기법으로 이 알고리즘은 1만큼의 시간만 걸린다고 쓴다. 이런 알고리즘을 가리켜 상수 시간(constant-time)알고리즘이라고 부른다.
이와 같이 최고차항을 제외한 모든 것을 들어내기 때문에, 수행 시간의 O표기는 훨씬 계산하기 간편하다. 이 표기법을 쓸 때 알고리즘의 시간 복잡도는 반복문에 의해 결정되기 때문에, 반복문들이 몇 번이나 실행되는지만을 보면된다.

O 표기법의 의미

O 표기법은 대략적으로 함수의 상한을 나타낸다는데 의미가 있다.
O 표기법이 수행 시간의 상한을 나타낸다는 사실을 통해 알고리즘의 최악의 수행 시간을 알아냈다고 착각할 수 있따. 하지만 O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있는 것은 아니다. 예를 들어 퀵 정렬의 최악의 수행 시간을 분석해 보면 최고차항이 N^2임을 알 수 있고, 따라서 퀵 정렬의 최악의 시간 복잡도는 O(N^2)이다. 그러나 평균 수행 시간을 계산해 보면 최고차항이 NlogN이고, 따라서 퀵 정렬의 평균 시간 복잡도는 최악의 경우와 달리 O(NlogN)이 된다.

시간 복잡도 분석 연습

두 가지 예제를 살펴보자.
selectionSort()는 선택 정렬(selection sort) 알고리즘을 구현한다. 선택 정렬은 모든 i에 대해 A[i ~ N-1]에서 가장 작은 원소를 찾은 뒤, 이것을 A[i]에 넣는 것을 반복한다.

void selectSort(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(vectoc<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;
                }
    	}
}

간단하게 최대 O(N)번 실행되는 for문이 두 개 겹쳐 있기 때문에 최종 시간 복잡도는 O(N^2)이라고 계산해도 된다. 선택 정렬의 시간 복잡도는 A[]에 포함된 원소들과는 상관 없이 A[]의 크기 N에 의해서만 결정되기 때문에 최악의 경우와 최선의 경우의 시간 복잡도가 같다.

insertionSort()는 삽입 정렬(insertion sort)의 구현을 보여준다. 삽입 정렬은 전체 배열 중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일을 반복하는 방식으로 동작한다. 처음부터 이미 정렬된 배열이 주어지는 경우가 삽입 정렬의 최선의 경우로 시간 복잡도는 O(N)이 된다. 반면 삽입 정렬의 최악의 경우는 역순으로 정렬된 배열이 주어지는 경우이다. 이 경우 O(N^2)이 된다.
입력이 임의의 순열이라고 할 때, 대부분읜 경우 삽입 정렬이 선택 정렬보다 빠르다. 이 비교는 실제 프로그램으로 구현해서 비교했을 경우에도 유효하며, 실제로 삽입 정렬은 흔히 사용하는 O(N^2)정렬 중 가장 빠른 알고리즘으로 알려져 있다.

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

알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것으로만 결정하지는 않는다. 가끔은 문제의 조건에 따라 그보다 더 정확한 시간 복잡도를 계산하는 것도 가능한데, 그 대표적인 예가 시간 복잡도의 분할 상환 분석(amortized analysis)을 사용하는 것이다.
N개의 작은 작업들을 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 사용할 수 있다. 이때 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다.

수행 시간 어림짐작하기

주먹구구 법칙

프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 한다. 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많다. CPU의 클럭 속도, 1클럭마다 수행할 수 있는 CPU 명령어의 수, 프로그램의 메모리 접근 패턴, 운영 체제와 컴파일러의 버전 등등 여러가지가 있다.
그러나 많은 경우에 시간복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적으로 짐작하는 것이 가능하다. 시간 복잡도는 프로그램의 수행 시간에 가장 큰 영향을 미치는 요소이기 때문이다. 앞에서 언급한 요소들은 프로그램의 수행 속도를 기껏해야 몇 배 차이나게 할 뿐이다. 그러나 알고리즘의 시간 복잡도가 달라지면 프로그램은 수천 배, 수만 배까지 빨라지거나 느려질 수 있다.

프로그래밍 대회 참가자들이 사용하는 주먹구구 법칙

  • 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.
    O(N^3) 알고리즘과 O(NlogN) 알고리즘을 예시로 보자.
    N에 10000을 대입하면 O(N^3)은 1억을 훨씬 초과하고, O(NlogN) 알고리즘은 1억에 훨씬 미치지 못한다.
    다만 시간 복잡도와 입력의 크기 외의 요소들이 프로그램의 수행 속도를 열 배정도는 쉽게 바꿔 놓을 수 있기 때문에 이 법칙을 적용할 때는 충분한 여유를 두는 것이 좋다.

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

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

문제의 특성 공부하기

계산 복잡도 이론은 각 문제의 특성을 공부하는 학문이다. 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타낸다.

출처

profile
정팔입니다.

0개의 댓글