- 알고리즘의 효율성을 논하게 되는 때는 입력의 크기가 충분히 클 때이다. 이 때, 점근적 분석을 하게 되며 이를 통해 나타난 시간과 입력의 함수 관계를 시간 복잡도라고 한다.
- 시간 복잡도가 높다는 말은 입력한 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 뜻이다.
- 알고리즘마다 최선의 수행 시간, 최악의 수행 시간, 평균적인 경우의 수행 시간(수행 시간의 기대치)이 있겠지만 주로 최악의 수행 시간과 수행 시간의 기대치를 중심으로 시간 복잡도를 판단하며, 따라서 Big-O Notation으로 표기한다. 이는 뒤에서 다뤄보도록 하자.
- 반복문이 시간 복잡도를 좌우한다.
점근적 표기
- 고등학교 때 배우는 무한의 개념(lim n→∞)과 비슷하다. 하지만 알고리즘에서 다루는 표기법은, 차수는 중요하되 계수는 중요치 않게 본다.
증가율 측면에서 볼 때 아래와 같다.
- logN < N < NlogN < N^2 < N^3 < 2^N
- logN < N < NlogN < N^2 < N^3 < 2^N
- 점근적 표기법은 모두, 점근적 의미에서 같다고 볼 수 있는 함수의 ‘집합’을 의미한다.
Θ-표기법(Theta)
Θ(f(n))은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합이다.
- Θ(N^2)는 N^2, 3N^2-50 등을 포함한다.
O-표기법(Oh)
O(f(n))은 점근적 증가율이 f(n)보다 작거나 같은 모든 함수의 집합이다.
- O(N^2)는 N^2, 3N^2-50 뿐만 아니라, 5N+15, 2NlogN+3N, 500 등을 포함한다.
- 앞서 설명한 Big-O Notation이 바로 이것이다.
Ω-표기법(Omega)
Ω(f(n))은 점근적 증가율이 f(n)보다 크거나 같은 모든 함수의 집합이다.
- Ω(N^2)는 N^2, 3N^2-50 뿐만 아니라, 5N^3+15, 2N^2logN+1 등을 포함한다.
그밖에 ‘엄밀한’ 표기법들
o-표기법(Little Oh)
- Big Oh가 아닌 Little Oh 표기법도 있다.
- Big Oh와의 차이점은, (1/2)N^2이 o(N^2)에 포함되지 않는다는 것이다.
- 즉, o-표기는 함수 기울기상의 여유 있는 상한을 나타낸다.
ω-표기법(Little Omega)
- Big Omega가 아닌 Little Omega 표기법도 있다. 이는 Little Oh와 반대의 의미다.
- Big Omega와의 차이점은, 2N^2이 ω(N^2)에 포함되지 않는다는 것이다.
- 즉, ω-표기는 함수 기울기상의 여유 있는 하한을 나타낸다.
점화식을 통해 재귀호출 알고리즘의 수행 시간 표현하기
반복 대치, 추정 후 증명, 마스터 정리라는 대표적인 세 가지 방법에 대해 알아보자.
반복 대치
- T(n)을 T(n-1)로 대치하고, T(n-1)을 T(n-2)로 대치하고, …, T(1)까지 대치해가는 방식을 사용해 점근적 복잡도를 구하는 방법이다.
예시로, n!를 구하는 데 소용되는 시간을 구해보자.
T(n) = T(n-1) + c = (T(n-2) + c) + c = ((T(n-3) + c) + c) + c ... = T(1) + (n-1)c = O(n)
- 병합정렬도 위와 같이 구하면, NlogN이 나옴을 알 수 있다.(참고로, 여기서 log는 밑이 2인 log을 의미)
추정 후 증명
- 식의 모양을 보고 복잡도를 추정한 다음, 이를 귀납적으로 증명하는 방법이다.
- 예시는 생략하겠다.
마스터 정리
특정한 모양을 가진 재귀식(아래 형태)에서 바로 결과를 알 수 있게 해주는 유용한 정리다.
병합 정렬이 대표적인 예로, a = b = 2, f(n) = n인 경우다.
a >= 1, b >= 1에 대해 위 형태의 점화식에서, N^(logba) = h(N)이라 할 때 f(n)과의 무게 비교를 통해 전체 복잡도를 알아볼 수 있다. 문병로 교수님의 책에는 “다항식의 비율로 압도한다”라는 표현이 쓰였다.
- 참고로, logba라고 위에 작성한 것은 ‘밑이 b인 log a’를 의도한 것이니 착오 없기 바란다.
직관적으로, 결과를 이해하자면 이렇다.
- h(N)이 더 무거우면 h(N)이 수행시간을 결정한다. Θ(h(N))
- f(N)이 더 무거우면 f(N)이 수행시간을 결정한다. Θ(f(N))
- 만일 이 둘이 같은 무게이면 h(n)에 logN을 곱한 것이 수행시간이 된다. Θ(h(N)logN)
[참고자료]
문병로(2018). 관계 중심의 사고법, 쉽게 배우는 알고리즘. 한빛아카데미.
주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행가능한 유한개의 일련의 명령을 순서적으로 구성한 것 다음의 조건을 만족한다 일반적으로 적용할 수 있는
알고리즘 설계기법은 존재하지 않음 비교적 많은 부류의 문제에 사용할 수 있는 기법으로는 greedy, divide and conquer, dynamic programming 등이 있음 순환적으로 문제를 푸는 방법 문제를 더 이상 나눌 수 없을 때까지 작은 문제로 나누고, 나누어진 작은 문제를 각각 해결한 후 결합하여 원래의 문제를 해결하는 방식 분할 정복을 적용한 알고리즘: 퀵정렬,
합병정렬, 이진탐색, 선택문제(n개의 원소중 i번째 작은원소 찾기...) ... 주어진 문제를 여러 개의 부분문제로 분할하고 가장 작은 부분부터 해를 구한뒤 이를 이용하여 입력크기가 큰 문제를 해결해 나가는 방법 동적 프로그래밍을 적용한 알고리즘: 플로이드 알고리즘(모든 쌍의 최단경로 찾기) ... 어떤 기준에 따라 전후단계의 선택과 상관없이 각 과정마다 최적해를 선택해나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라 기대하는 방법 따라서 적용범위는 제한적이다. 욕심쟁이 방법을 적용한 알고리즘 : 프림 알고리즘(최소비용 신장트리), 크루스칼 알고리즘, 데이크스트라 알고리즘(단일 출발점에서 최단경로 구하기),
거스름돈 문제, 배낭문제 가게에서 고객에게 돌려준 거스름돈이 T 만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법은? 동전은 500원, 100원, 50원, 10원, 5원, 1원의 6종류가 있다고 가정 욕심쟁이 해법은 액면가가 큰 동전부터 뽑아서 거스름돈을 만드는 것 최대 용량이 M인 배낭 하나와 무게 Wi, 이익Pi인 물체 n개가 있을 때, 배낭에 담을 물체의 이익을 최대화 하는 방법은?알고리즘 기초
알고리즘 소개
알고리즘 기본개념
알고리즘 설계
분할정복 (divide and conquer)
동적 프로그래밍 (dynamic programming)
욕심쟁이 (greedy)
욕심쟁이 해법은 단위 무게당 가장 이익이 많이 나는 물체를 순서대로 반복해서 넣으면 된다.
알고리즘 분석
알고리즘은 정확하고 효율적이어야 한다
정확성 분석
알고리즘에 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성해야 한다
효율성 분석
알고리즘을 수행하기 위해서 필요한 컴퓨터 자원 (메모리, 주변창치, 수행시간)의 측정을 통해 이루어짐
공간 복잡도 (space complexity)알고리즘을 실행시켜 완료까지 필요한 총 메모리의 양을 말함 (정적 공간 + 동적 공간)
시간 복잡도알고리즘을 실행시켜 완료하는 데 걸리는 시간
일반적으로 알고리즘의 총 수행시간은 단위 연산이 몇 번 수행되는가에 거의 비례한다
알고리즘의 수행시간은 주어진 입력 데이터의 상태에 영향을 받는다. 따라서 다양한 형태의 입력에 따라 수행되는 시간의 평균, 최선, 최악을 구하는 것이 필요하다.
점근성능
알고리즘 성능은 입력의 크기에 따라 달라지므로, 데이터의 양이 무한히 많아지는 상황을 전제로 알고리즘의 성능을 표현하는 것이 바람직하다
알고리즘의 성능은 단위 연산의 실행 빈도수를 통해 유도된 다항식의 수행시간에 대해서, 최고차항만을 이용하여 표시된다.
최고차항을 이용한 성능 표기값은 어림값이므로 정확한 성능을 표현할수는 없을지라도 알고리즘 간의 성능비교가 용이하고 데이터 개수의 증가에 따른 알고리즘 수행시간 증가추이를 쉽게 파악할 수 있다.
점근 성능을 표기하는 대표적인 방법으로 다음 세 가지 방법이 있다
함수 f와 g를 각각 양의 정수를 갖는 함수라 하면
- Big-oh (O): 어떤 양의 상수 c와 n0가 존재하여 모든 n >= n0에 대하여 f(n) <= cg(n)이면 f(n) = O(g(n))이다
- Big-omega (Ω): 어떤 양의 상수 c와 n0가 존재하여 모든 n >= n0에 대하여 f(n) >= cg(n) 이면 f(n) = Ω(g(n))이다
- Big-theta (Φ): 어떤 양의 상수 c1, c2와 n0가 존재하여 모든 n >= n0에 대하여 c1g(n) <= f(n) <= c2g(n)이면 f(n) = Φ(g(n))이다
함수 f(n)은 일반적으로 알고리즘의 수행시간을 나타낸다
이때 f(n)이 O(g(n))이라면, n이 무한히 커지더라도 f(n)의 값은 결국 g(n)의 상수 배보다 적다는 것을 의미한다 다시말해 O 표기법의 성능은 최악의 경우에 대해서도 알고리즘의 수행시간이 O(g(n))이 되고 g(n)을 함수의 점근적 상한이라 표현한다.
Ω(g(n))은 f(n)의 점근적 하한을 의미하며, 알고리즘 최선의 경우를 의미한다.
f(n)이 g(n)을 점근적 상한과 하한을 동시에 갖는경우 Φ 표기법을 사용한다.
예를 들어 복잡도 함수가 O(n^3)이라는 것은 점근적 상한 수행 시간이 n^3을 넘지 않는 함수 f(n)의 집합이다. 따라서 f(n)이 반드시 3차 함수일 필요는 없고 3차 함수 아래에 놓이기만 하면 된다
점근성능의 효율성
주어진 함수 f(n)의 최고차항으로 표시한 점근성능의 연산시간 순서는 다음과 같다
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < ... < O(2^n) < O(n!)
순환 알고리즘의 성능 (recursive)
이진 탐색(binary search) 알고리즘의 경우 주어진 리스트 중앙값과 탐색값의 비교를 통해 크기가 반으로 줄어든 리스트를 대상으로 동일한 이진 탐색과정을 반복한다.
이와 같이 알고리즘의 수행과정에서 자신의 알고리즘을 다시 수행하는 형태를 순환/재귀(recursive) 알고리즘이라 부른다.
순환 알고리즘의 수행시간을 나타내기 위해 점화식이 사용된다.
n은 1보다 큰 경우 T(n)을 다음과 같은 점화식으로 표현할 수 있다.
T(n) = T(n/2) + c2, T(1) = c1
위 식을 전개하여 점화식의 폐쇄형을 구하면 다음과 같다
T(n) = T(n/2) + c2 = T(n/4) + c2 + c2 = T(n/2^2) + 2c2 = T(n/8) + c2 + c2 + c2 = T(n/2^3) + 3c2 = T(n/2^(k-1)) + (k-1)c2 = T(1) + kc2 (n = 2^k 인경우 정의 가능 k = log2n) = c1 + kc2 = c1 + c2log2n
이를 점근 표기법으로 나타내면 O(logn)이 된다
몇 가지 기본적인 알고리즘의 점화식에 대한 폐쇄형을 정리하면 다음과 같다
| T(n) = T(n-1) + Φ(1), n >= 2 | T(n) = Φ(n) | |
| T(n) = T(n-1) + Φ(n), n >= 2 | T(n) = Φ(n^2) | 퀵정렬(최악) |
| T(n) = T(n/2) + Φ(1), n >= 2 | T(n) = Φ(log2n) | 이진탐색 |
| T(n) = T(n/2) + Φ(n), n >= 2 | T(n) = Φ(n) | |
| T(n) = 2T(n/2) + Φ(1), n >= 2 | T(n) = Φ(n) | |
| T(n) = 2T(n/2) + Φ(n), n >= 2 | T(n) = Φ(nlog2n) | 퀵정렬(최선), 합병정렬 |