알고리즘 분석 및 복잡도 측정

목차

◎본 챕터의 목적

◎알고리즘 종류에 따른 처리속도의 차이

◎알고리즘 복잡도에 따른 능률성 비교

◎비효율적 알고리즘과 효율적 알고리즘의 차이 및 분석(I)

◎비효율적 알고리즘과 효율적 알고리즘의 차이 및 분석(II)

◎BigO, O표기법의 정의 및 예

◎Ω표기법의 정의 및 예

◎θ표기법의 정의 및 예

◎연습문제 및 풀이

◎ 요 약

본문내용

정의에 의해서, n인 모든 n에 대하여 다음 부등식이 성립하는 n과 c가 있으면 된다.
c
c를 1로 정하고 를 0으로 정했을 때, 0인 모든 에 대하여, 항상 성립된다.
이해 : Ω는 “at least as fast as” 즉 최소한 같거나, 더 빠르게 증가한다는 의미다.
-10-
◎ θ표기법의 정의 및 예
-θ의 정의 : 인 모든 정수 n에 대하여 ××을 만족하는 세정수 와 가 존재 할 때, 우리는 이라고 정의한다. 다시 말해서, 임의의 복잡도 함수에 대하여, ∩이 성립되는 것을 말한다.
여기에서는 과 이 같은 비율로 증가하는 함수를 말한다. 정의에서 보여진
×× 에서 처럼 는 상한을 만족함과 동시에 하한을 만족한다. 그러므로 이나 보다 더 정확한 한계치를 나타낸다.
다음 그림 1-2는 , , 의 정의를 이해를 돕기 위하여 그림으로 나타낸 것이다.
-11-
◎ 연습 문제
연습문제1) n센트를 25센트,10센트,5센트,1센트로 알고리즘이 비교횟수에 관하여 O(n) 복잡도를 갖음을 증명하여라.
연습문제2) 의 시간 복잡도를 가지는 알고리즘이 1초에 입력 100을 처리한다. 이 알고리즘이 100초에 처리할 수 있는 입력의 갯수는 얼마인가.
연습문제3)다음 알고리즘의 시간 복잡도를 구하라.
void algorithm_N1(int n){
int i,j,x,y;
for(i=1;i<=n;i++)
if(i%2 == 1) {
for(j=i;j<=n;j++)
x = x + 1;
for(j=i;j<=n;j++)
y = y + 1;
}
}
연습문제4) 다음의 복잡도 함수들을 크기에 대한 오름차 순으로 정렬하시오.
, , , , , , ,
연습문제5) 함수 f가 다음과 같이 정의될 때, 다음 물음에 답하시오.
= 0, n = 1
= n 2
를 구하시오.
-12-
◎ 해 답
연습 문제1) 주어진 문제를 알고리즘으로 구현하면 다음과 같다.
void Change_coins (int n){
n25 =0;
for(i=0;i {
if(n - 25 > 0)
{
n = n - 25;
25n++;
}
else
break;
}
n10 =0;
for(i=0;i {
if(n - 10 > 0)
{
n = n - 10;
10n++;
}
else
break;
}
n5 =0;
for(i=0;i {
if(n - 5 > 0)
{
n = n - 5;
5n++;
}
else
break;
}
n1 = n;
}
중첩되어있지 않은 4개의 루프로 이루어져 있으므로, 이 알고리즘의 시간 복잡도는 4n이다. 그러므로 O(n)임이 증명 되었다.
연습 문제2)은 이 시간에 비례한다는것을 의미한다. 그러므로
= k × T 이다. (이때 T를 시간(1초), k를 비례상수로 놓는다.)
입력이 100이므로, 다음공식은
= k × 1sec 가 된다. 그러므로
k = 가 된다.
이것을 다시 문제의 공식에 대입하면,
= × 100sec 을 풀면은
= 1000이 된다.
그러므로 이 알고리즘이 100초동안 풀 수 있는 입력의 갯수는 1000개가 된다.
-13-
연습 문제3) 첫 for루프에서 n번의 반복을 하므로 O(n)이 된다.
두번째 for루프에서
i=1일 때, 1,2,...n만큼 루프를 돈다. n
i=2일 때, 2,3,...n만큼 루프를 돈다. n-1
i=3일 때, 3,4,...n만큼 루프를 돈다. n-2
:
:
i=n-2일 때, n-2, n-1, n3번 루프를 돈다. 3
i=n-1일 때, n-1, 2번를 돈다. 2
i=n 일 때, n 1번 루프를 돈다. 1
총 n/2만큼 반복을 하는 루프가 2개가 중첩이 안된 상태로 있다.
그러므로 2×n/2 이므로, O(n)이 성립된다.
첫 번째 루프와 두번째 루프가 중첩이 되어 있으므로, 두개를 곱하면,
O()이 왼다.
연습 문제4)
, , , , , , ,
연습 문제5)
n = 25이므로, n 2에 속한다.
그러므로 = 공식에 대입하면, = 가 된다.
는 n 2에 속하므로 = 가 된다.
계속 반복하면은 가 된다.
는 n = 1에 속하므로, 는 0이 된다.
그러므로 + 1 = 1이 된다.
그 윗 단계인 는 1이 되고, +1 = 2가 된다.
이런 방식으로 계속 계산하면 답은 6이 된다.
-14-
◎ 요 약
알고리즘(Algorithm)의 정의를 “어떤 주어진 문제를 해결하기 위한 가장 합리적인 방법”, 또는 “명확성 효과성 종료성을 모두 만족하는 명령어들의 순서”라 할수 있다.
어떤 주어진 문제를 향하여 가장 정확히 가장 효과적인 알고리즘을 선택하기 위해서는 명령어들을 배열 하기 위하여서는 각 알고리즘을 정확히 분석 및 복잡도를 보다 정확히 측정할 필요가 있다
그러므로 더욱 효과적인 알고리즘을 설계 및 비교하기 위하여 우리는 복잡도 라는 것을 계산 및 이용한다.
복잡도에는 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)가 있다. 하지만 공간 복잡도는 시스템 사양 및 여러 가지가 큰 변수가 되므로 흔히 우리는 시간 복잡도로 알고리즘의 효율성을 측정한다.
시간 복잡도는 쉽게 얼마만큼 반복적 연산이 되느냐로 이해할 수 있는데, 가장 효율적인 측정 방법에는 크게 3가지(BigO, Ω, θ)로 나뉘어진다.
-BigO의 정의① : 인 모든 정수 n에 대하여 ×를 만족하는 두 정수 와 가 존재할 때, 우리는 =이라고 정의한다. 그리고 이러한 복잡도 함수들의 집합 를 의 big-oh, 혹은 O-표기라고 한다. 다시 말해서 만약 이면, 우리는 이 의 big-oh라고 한다.
-Ω의 정의 : 인 모든 정수 n에 대하여 ×를 만족하는 두 정수 와 가 존재할 때, 우리는 =이라고 정의한다. 그리고 이러한 복잡도 함수들의 집합 를 의 오메가 (omega)와 같다고 말하며, 이와 같이 복잡도를 나타낸 것을 오메가 표기라고 한다.
-θ의 정의 : 인 모든 정수 n에 대하여 ××을 만족하는 세정수 와 가 존재 할 때, 우리는 이라고 정의한다. 다시 말해서, 임의의 복잡도 함수에 대하여, ∩이 성립되는 것을 말한다.
θ()는 상한을 만족함과 동시에 하한을 만족한다. 그러므로 이나 보다 더 정확한 한계치를 나타낸다.
-15-

키워드

빅오,   bigo,   big O ,   알고리즘,   복잡도,   효율적