피보나치 수열 : 재귀 알고리즘

  • T(n) = fib(n)을 계산하기 위해서 fib()함수를 호출하는 횟수
  • T(0) = 1, T(1) = 1
  • T(n) = T(n-1) + T(n-2) (for ≥ 2)

재귀 알고리즘의 증명

알고리즘 분석

  • 시간복잡도(Time Complexity Analysis) 분석
    • 입력 크기(Input Size)를 정의한다
      • 배열의 크기 등
    • 단위 연산(Basic Operation)을 정의한다.
      • 비교문(Comparison), 지정문(Assignment) 등
  • 알고리즘의 시간 복잡도 분석은 입력크기를 기준으로 단위연산을 몇 번 실행하는지 구하는 것이다.
  • 어떤 겨웅에는 입력크기 및 입력 값에도 좌우된다.
    • 순차검색에서 검색요소가 배열의 첫 번째 요소 : 1번 수행
    • 배열에 없는 경우 : n번 실행

알고리즘 분석 종류

  1. 일정 시간 복잡도 분석(Every-case time complexity analysis)
  • 복잡도는 입력 크기에만 종속
  • 입력 값과는 무관하게 복잡도는 일정 (예 : 배열의 원소 모두 더하기)
  1. 최악의 경우 분석(Worst-case analysis)
  • 복잡도는 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최대(최악)인 경우 선택
  1. 평균의 경우 분석(Average-case analysis)

💡 Worst-case의 비중이 극히 적을 때 사용

  • 입력크기와 입력 값 모두에 종속
  • 모든 입력에 대해서 단위연산이 수행되는 기대치(평균)
  • 각 입력 값에 대해서 확률 할당이 가능
    • 확률에 따라 기대치가 다르게 계산될 수 있음
  • 일반적으로 최악의 경우보다 계산이 복잡
  1. 최선의 경우 분석(Best-case analysis)
  • 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최소(최선)인 경우 선택

교환 정렬 알고리즘

int[] arr = {7,3,2,5};
for(int i = 0 ; i < arr.length ; i++){
    for(int j = i+1 ; j < arr.length ; j++){
        if(arr[i] > arr[j]){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
  • 단위연산 : 조건문 (S[j]와 S[i]의 비교)
  • 입력크기 : 정렬할 항목의 수 n
  • 최악의 경우 분석 :
    • 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다.
    • 최악의 경우
      • 조건문이 항상 참이 되는 경우
      • 입력배열이 거꾸로 정렬되어 있는 경우
  • T(n) = (n-1) + (n-2) + (n-3) + … + 1 = (n-1)n/2

순차 검색 알고리즘

  • 단위연산 : 배열의 아이템과 키 x와 비교 연산 (S[location] ≠ x)
  • 입력크기 : 배열안에 있는 아이템의 수 n
  • 최악의 경우 분석
    • x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우, 단위 연산이 n번 수행된다.
    • 따라서, W(n) = n
  • 평균의 경우 분석(경우 1) : x가 배열 S안에 있는 경우만 고려
    • $1≤k≤n$에 대해서 x가 배열의 k번째 있을 확률 = 1/n
    • x가 배열의 k번째 있다면, x를 찾기 위해서 수행하는 단위연산의 횟수 = k
  • 평균의 경우 분석(경우 2) : x가 배열 S안에 없는 경우도 고려
    • x가 배열 S안에 있을 확률을 p라고 하면,
      • x가 배열에 있을 확률 = p(x가 배열의 k번째 있을 확률 = p/n)
      • x가 배열에 없을 확률 = 1 - p

정확도 분석

  • 알고리즘이 의도한 대로 수행되는지를 증명하는 절차
    • 즉, 알고리즘이 정확하게 수행되는지를 증명하는 절차
  • 정확한 알고리즘이란?
    • 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘
  • 정확하지 않은 알고리즘이란?
    • 어떤 입력에 대해서 멈추지 않거나, 또는
    • 틀린 답을 출력하면서 멈추는 알고리즘