효율적인 알고리즘 개발의 중요성

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

따라서, 순차검색 알고리즘의 경우 입력배열의 값에 따라서 검색하는 횟수가 달라지므로, 모든 경우 분석은 불가능하다.

정확한 알고리즘이란?

• 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘

정확하지 않은 알고리즘이란?

• 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘