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

 

1. 알고리즘의 시작

효율적인 알고리즘을 만들기 위해선 알고리즘의 속도를 측정할 수 있어야 한다.  알고리즘의 속도를 알 수 있어야 더 좋은 알고리즘인지 판단할 수 있기 때문이다.  알고리즘의 속도를 측정하는 방법으로는 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는것이다.  하지만 단순이 동일한 입력으로 어떤 알고리즘이 빠르다는 것을 단정지을 수 없다.  

 

첫번째, 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 여러 요소들이 영향을 미친다.

 

두번째, 다른 입력값에 대한 프로그램의 수행 시간을 반영할 수 없다.

 

앞에서 동일한 입력으로 어떤 알고리즘이 빠른지를 판단한다고 했는데, 그 동일한 입력값이 다른 값으로 바뀐다면?

입력의 크기나 특성에 따라 수행 시간이 달라질 수 있다는 것이다.

 

시간 복잡도는 반복문이 지배한다!

'반복문이 지배한다!'  알고리즘에서의 지배한다는 무슨 뜻일까?

예를 들어, 어느 한 공장에서 상품을 생산한다. 이때 생산기계 A와 생산기계 B가 있고 누가 더 상품 100개를 빨리 만들 수 있을지 비교해보자.

• 생산기계 A는 기계준비 시간이 1분이고 1시간에 10개의 상품을 생산할 수 있다.
• 생산기계 B는 기계준비 시간이 10분이고 1시간에 60개의 상품을 생산할 수 있다.

기계준비 시간이 1분이라고 해서 사람들이 생산기계 A가 더 효율적인것일까? 결국 상품을 100개를 더 빨리 만들 수 있는 기계는 생산기계 B 이다.

 

이와 같이 한 가지 항목이 효율을 좌지우지하는 것을 지배한다 (dominate) 라고 표현한다.

 

그러면 다시 알고리즘으로 돌아가서 알고리즘의 수행 시간을 지배하는 것은 무엇일까?

 

반복문이다.

 

따라서 알고리즘의 수행 시간이 반복문이 수행되는 횟수로 측정된다.

 

 

2. 선형 시간 알고리즘

선형 시간 알고리즘은 입력된 자료를 모두 검사하고 입력의 크기에 비례해 시간이 걸린다. 

선형 시간 알고리즘의 대표적인 예시에는 이동 평균이 있다.

 

이동 평균 (moving average)은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준이다.

시간에 따라 관찰된 숫자들이 주어질 때 M에 대한 이동 평균은 마지막 M개의 관찰 값의 평균이다.

또한 새 관찰 값이 나오면 M에 대한 이동 평균은 새 관찰값을 포함한다.

 

예시 코드는 이해하는데 시간이 조금 걸릴거 같아 작성하지 않았다.

 

 

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

선형 이하 시간 알고리즘이란?

선형 이하 시간 알고리즘은 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘을 말한다.

 

선형 이하 시간 알고리즘은 선형 시간 알고리즘보다 빨리 동작한다.

그런데 2번 글에서 말했듯이 선형 시간 알고리즘은 입력된 자료를 모두 검사하고 입력의 크기에 비례에 시간이 걸린다.

만약 선형 시간 알고리즘보다 더 빨리 동작한다면 입력된 자료를 다 보지 않는다는 뜻인데 이 알고리즘은 어떻게 동작할 수 있을까?

 

예를 들어, 아기의 성장을 알고싶어 지금까지 시간순으로 정렬된 10만장의 사진을 찍었고 아기가 걸어다닐 수 있을때를 찾고 싶다고 가정하자.

여기서 10만장의 사진을 모두 보는 것보다 더 효율적인 방법이 있다. 

아기의 성장이 반대로 갈 일은 없으니 10만장의 사진을 절반으로 나눠서 가운데 사진부터 보는 것이다.  확인할때 마다 장수가 절반으로 줄어드니 17장의 사진만 확인하면 아기가 걸어다녔을 시점을 찾을 수 있다.

따라서 입력된 자료를 다 보지 않고도 알고리즘이 동작할 수 있는 것이다.

 

선형 이하 시간 알고리즘의 시간 복잡도

선형 이하 시간 알고리즘의 시간 복잡도와 알맞는 함수는 어떤걸까?

 

로그함수이다.

logaN = k, a^k = N

 

이 예시에서는 계속 절반으로 나누고 10만장의 사진을 검사하기 때문에 알고리즘 시간 복잡도는 log2N이다.

 

 

이진 탐색

 

앞에서 선형 이하 시간 알고리즘의 걸어다니는 아기 사진 찾기 예시를 들고 해결 방법을 생각해보았다.

 

이 예시에서 썼던 알고리즘이 바로 이진 탐색이다.

 

이 문제를 코드로 작성해야한다면 어떤 식으로 작성하면 좋을까?

 

길이 N인 정수 배열 A를 만들고 시간 순서대로 사진 N개를 담는다.  그리고 아기가 걸을 수 있을때를 1로, 걷지 못할때를 0으로 한다. 그러면 아기가 걸을 수 있을때의 사진부터 배열이 1로 변할 것이다.

 

A = {0, 0, 0, ..., 0, 0 , 1, 1, 1, ... 1, 1}

 

그리고 이진 탐색 함수 binsearch()를 통해 배열 A의 0에서 1로 변하는 시점을 찾으면 된다.

 

 

4. 지수 시간 알고리즘

다항 시간 알고리즘

다항 시간 알고리즘은 반복문의 수행 횟구를 입력 크기의 다항식으로 표현 할 수 있는 알고리즘이다.

 

5. 시간 복잡도

시간 복잡도란?

시간 복잡도 (time complexity)는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다.

여기서 기본적인 연산은 더 작게 쪼갤 수 없는 최소 크기의 연산이다. 

 

시간 복잡도가 높다는 것은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 것이다. 

 

다른게 해석하면 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다.

 

입력의 크기가 매우 작으면 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수 있지만, 반대로 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 시간 복잡도가 높은 알고리즘과 비교했을때 훨씬 빠르게 동작한다.

 

 

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

입력의 크기가 수행 시간에 영향을 미치지만 입력의 종류도 수행 시간에 영향을 미친다.

 

이해를 위해 코드로 예시를 들어보자.

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이다. 

 

O 표기법 (Big-O Notation)

우리는 O 표기법을 통해 시간 복잡도를 더 간단하게 표기할 수 있다.  

O 표기법은 주어진 함수에서 가장 빨리 증가하는 항만 남기고 나머지는 다 버리는 표기법이다.

 

 

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

예시 생각해보기

 

7. 계산 복잡도 클래스

• P 문제 : 다항 시간 알고리즘이 존재하는 문제이다.
• 계산 복잡도 클래스 (complexity class) : P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합이다.
• NP 문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제이다.
• P=NP 문제 : P와 NP가 같은지를 확인하는 문제이다.

설명 추가하기

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략