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

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

0. 알고리즘이란?

- 알고리즘: 어떤 한 작업이 주어졌을 때 컴퓨터가 그 작업을 해결하는 방법으로, 하나의 같은 문제를 해결하더라도 다양한 경우의 수를 가진 알고리즘들이 나타날 수 있다.

* 좋은 알고리즘의 평가 기준

- 시간: 알고리즘이 적은 시간을 사용한다면 더 빠르게 동작한다.

- 공간: 알고리즘이 적은 공간을 사용한다면 더 적은 용량의 메모리를 사용한다.

그러나 이 두 가지가 상충한다면 더 우선시 되어야 하는 것은 알고리즘의 ‘시간’이며, 메모리 사용량을 희생하여 수행 속도를 높이는 ‘동적 계획법’이 그 대표적인 예이다.

 

1. 도입

: 보다 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 알고리즘의 속도 측정 방법을 정하는 것으로, 두 알고리즘의 속도를 비교하는 가장 직관적 방법은 각각의 알고리즘을 프로그램으로 구현하여 구현된 프로그램의 수행 시간을 측정하는 것이다.

그러나, 이렇게 구현된 프로그램의 수행 시간은 프로그래밍에 사용된 언어, 프로그램을 동작시키는 컴퓨터의 하드웨어, 운영체제, 컴파일러 등 수많은 요소에 의해 바뀔 수 있기 때문에 적합한 측정 방법이라 할 수는 없다.

cf) C++에서 크기가 큰 구조체를 함수의 인자로 넘길 때는 reference 형태로 넘겨 주는 것이 좋다. Vector 전체를 넘길 경우, vector를 모두 읽어오는 것부터 많은 시간을 잡아먹기 때문으로, reference(in C++) 혹은 pointer(in C)의 형태로 넘기는 것이 시간적으로 더 유리하다.

 

“반복문이 지배한다”

여러 비교에 있어서 한 가지 항목이 다른 항목들의 대소를 지배(dominate)하는데, 알고리즘에서는 ‘반복문’이 시간 복잡도와 수행 시간을 지배하게 된다.

 

 

2. 선형 시간 알고리즘

Input의 크기 N에 정비례하는 수행 시간을 가지는 ‘선형 시간 알고리즘’

 

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

입력으로 주어진 자료에 대해 미리 알고 있는 경우, 선형 시간 알고리즘보다 빠르게 동작하는 알고리즘의 구현이 가능 (log N)

l  이진탐색(Binary Search): 10만 개의 자료 중 5만 번째 자료 확인 à 7만 5천번째 자료 확인 à … à 대략 17개의 자료만으로 원하는 결과 얻어낼 수 있음

l  Binsearch(A[ ], x) = 배열 A[ ]에서 x를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환한다. 즉, 배열 내 x가 존재할 경우 첫 번째 x의 위치를, 없는 경우 x보다 큰 첫 번째 원소를 반환한다. 
ex {0, 0, 0, 0, 0, …, 0, 1, 1, 1, …, 1, 1, 1}

* cf. 결국에는 선형 시간?

1)    배열을 넘긴다고 하였지만 사실은 배열을 넘기는 것이 아니다. 확인하고 싶은 위치의 자료만 판단하면 되는 구조

2)    ‘10만 개의 자료를 미리 정렬한다는 의미’는 이 문제의 해결 뿐 아니라 다른 문제의 해결을 위해서도 쓰일 수 있는 것이기 때문에 문제 해결의 일환으로 보지 않는다.

 

4. 지수 시간 알고리즘

l  다항 시간 알고리즘: 반복문의 수행 횟수인 N에 따라 달라지는 다항 시간 알고리즘. 다항 시간 알고리즘 간에 발생하는 지수의 차이에 따라 수행 시간에 큰 차이가 발생

l  가장 단순하게 최소값을 구하는 방법은 재귀 알고리즘 형태의 구현!

l  지수 시간 알고리즘: 지수의 증가에 따른 수행 시간의 증가

l  다항 시간 알고리즘의 구현이 가능한 문제는 쉬운 문제, 그렇지 않은 문제는 어려운 문제로 단순하게 분류할 수 있음.

l  숫자의 개수가 아닌 숫자의 크기에 따라 수행 시간이 달라지는 알고리즘들 또한 지수 수행 시간을 가질 수 있음
ex) 소인수 분해: 입력 값이 소수인 경우, n-1 번의 실행 횟수를 가지게 됨.

* cf. 과연 소인수 분해가 지수 수행시간을 가지는가?

이진 탐색, 이동 평균 계산 등은 입력의 값들이 일정 범위 내에 있기 때문에 입력의 개수가 메모리에서 차지하는 공간이 직접적으로 비례한다.

그러나, 소인수 분해 문제에서는 입력 값에 따라 알고리즘의 동작이 변화하기 때문에 숫자의 특정이 불가능하다. 입력의 값이 커지면 숫자를 저장하는 필요한 메모리의 공간 증가하게 되는 것이다. 이에 따라 Input값이 차지하는 메모리 내 비트의 수가 증가하여 수행 시간이 증가하게 되는 현상이 발생할 수 있게 된다..

* 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가

 

5. 시간 복잡도

l  기본적인 연산: 더 작게 쪼갤 수 없는 최소 크기의 연산(대입, 사칙연산, 대소 비교 등)

l  반복문이 포함되는 순간, 그 연산은 기본적인 연산이 아니게 됨

l  입력 크기에 따라 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수 있음
ex) 반복문을 여러 개 중첩하더라도 입력값이 작으면 반복문이 적은 알고리즘보다 좋은 성능을 낼 수 있는 경우가 생김

l  최악의 수행 시간, 수행 시간의 기대치를 기준으로 알고리즘을 작성하는 것이 보편적

l  점근적 시간 표기(Big - O 표기)

: 식에 존재하는 상수 등은 고려하지 않고, 가장 빨리 증가하는 항인 반복문의 반복 수만 고려한 표기 방법

* 특이 알고리즘:
- N²M + N log M + NM^2 = O(N²M + NM²)
à N²M과 NM² 중 어느 식이 더 커질 지 모르기 때문에 두 식 모두 표기

- 42 = O(1) à 상수 시간 알고리즘

l  Big - O 표기법은 알고리즘의 수행 시간을 간단히 나타내는 표기법일 뿐, 최악의 수행 시간과 관련 있는 것은 아니다.

 

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

l  주먹구구 법칙

: 시간 복잡도와 입력 크기로 대략적 수행 시간 예측이 가능한데, 1초당 반복문의 수행 횟수가 1억을 넘어가면 모든 문제에서 시간 제한을 초과할 가능성이 있다.

 

l  추가적으로 고려해야 할 요소

1)    시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: Big - O표기법의 경우 상수나 최고차항 이외의 항들을 모두 지워버리므로, 실제 프로그램의 수행 속도는 달라질 여지가 다분함

2)    반복문의 내부가 복잡한 경우: 반복문의 내부가 복잡하거나, 단순하면 Big – O의 예상치와는 다르게 작동하게 될 수 있음

3)    메모리 사용 패턴이 복잡한 경우: 하드웨어적으로 캐시의 사용은 시간 복잡도에는 영향을 미치지 않지만, 수행 속도에 영향을 미치게 된다. 따라서 캐시의 사용 여부에 따라 프로그램의 수행 시간 차이를 보일 수 있음

4)    언어와 컴파일러의 차이: C++의 최적화의 사용 여부 등 언어와 컴파일러에 따라 수행 시간의 차이가 발생하게 됨

 

7. 더 읽을거리

마스터 정리(Master Theorem): 재귀적 알고리즘의 시간 복잡도를 계산하는 수학적 정리