1.2 효율적인 알고리즘 개발의 중요성
계산한 호출 횟수의 검증
정리 : 재귀적 알고리즘으로 구성한 재귀 트리의 마디의 수를 T(n)이라고 하면, n>=2인 모든 n에 대하여 T(n) > 2^n/2이다.
피보나치 수 구하기 알고리즘 (반복적 방법)
int fib2(int n) //n을 6이라고 가정
{
index i;
int f[0..n];
f[0] =0;
if (n>0)
{
f[1] =1;
for (i =2; i<=n; i++)
f[i] = f[i-1] +f[i-2];
}
return f[n];
}
횟수 = n+1번
반복 알고리즘은 수행속도가 훨씬 빠르다.
- 이유: 중복 계산이 없음
계산하는 항의 총 개수
- T(n) = n+1
- 즉, f[0]부터 f[n]까지 한번씩 만 계산
알고리즘을 배워야 하는 이유
알고리즘이 반복되고, 알고리즘의 입력 수가 증가할수록 걸리는 시간은 기하급수적으로 늘어나기 때문이다.
1.3 알고리즘 분석(Analysis)
시간 복잡도 분석
- 입력크기의 값에 대한 단위연산 (+,-,if,=이 몇번?)의 수행 횟수를 결정하는 절차
분석 방법의 종류
- 모든 경우 분석
- 입력크기에만 종속
- 입력값과는 무관하게 결과 값은 항상 일정 - 최악의 경우 붕석
- 입력크기와 입력 값 모두에 종속 (순차탐색의 경우를 생각하면 됌)
- 단위연산이 수행되는 횟수가 최대인 경우 선택 - 평균의 경우 분석
- 입력크기와 입력 값 모두에 종속
- 모든 입력에 대해서 단위연산이 수행되는 기대치(평균치)
- 각 입력에 대해서 확률 할당 가능
- 일반적으로 최악의 경우보다 계산이 복잡 - 최선의 경우 분석
- 입력크기와 입력 값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택
알고리즘 1.2 : 배열 덧셈
number sum (int n, cost number S[])
{
index i;
number result;
result = 0;
for (i =1; i<=n; i++)
result = result + S[i];
return result;}
//예시를 n에 5대입 해보면 됌.알고리즘 1.2 : 배열 덧셈(시간복잡도 분석)
단위 연산 : 덧셈
입력크기 : 배열의 크기 n
모든 경우 분석 :
- 배열 내용에 상관없이 for-루프가 n번 반복된다.
- 각 루프마다 덧셈이 1회 수행된다.
- 따라서, n에 대해서 덧셈이 수행되는 총 횟수는 T(n) =n이다.
- 배정문, 지정문 == (=기호라고 보면 됌)
알고리즘 1.3 : 교환정렬
- 문제: 비내림차순으로 n개의 키를 정렬 => 올림차순으로 생각하면 됌
- 입력 : 양수 n, 배열 S[1..n]
- 출력: 비내림차순(올림차순으로 보면 됌) 으로 정렬된 배열
- 알고리즘
void exchangesort(int n, keytype = S[])
{
indext i, j;
for(i=1; i<=n-1; i++)
for(j=i+1; j<=n; j++)
if(S[j] < S[i])
exchange S[i] and S[j]; }(n에 5를 대입한다는 가정을 해서 보면 이해하기 쉽다)
- 조건문(S[j]와 S[i]의 비교)
모든 경우 분석은 수행될 때마다 조건문 1번씩 수행함으로 총 수행 횟수는
T(n)=(n-1)+(n-2)+...+1=(n-1)n/2 - 교환하는 연산(exchange S[j] and S[i])
조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다
최악의 경우 = 조건문이 항상 참(true)이 되는 경우
=입력 배열이 거꾸로 정렬되어 있는 경우
T(n)= (n-1)n/2
따라서, 순차검색 알고리즘의 경우 입력배열의 값에 따라서 검색하는 횟수가 달라지므로, 모든 경우 분석은 불가능하다.
정확한 알고리즘이란?
- 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘
정확하지 않은 알고리즘이란?
- 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘
정진, "어제보다 더 나은 오늘이 되자"