[알고리즘] 알고리즘 분석

알고리즘 분석

정확성 분석

• 유효한 입력에 대해 유한 시간 내 정확한 결과의 생성 여부
  
• 수학적 기법을 사용한 이론적인 증명 과정
  
  

효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정/평가
  
• 공간 복잡도
  
  • 메모리의 양 = 정적 공간 + 동적 공간
    
• 시간 복잡도
  
  • 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간
    
    

시간 복잡도

• 알고리즘 수행시간 = ∑{각 문장이 수행되는 횟수}
  

• 실행시켜 실제 수행시간을 측정하는 방식은 실행 환경에 종속적이며 일반성이 결여 됨
  
  

• 수행시간에 영향을 미치는 요인
  
  1. 입력크기 및 개수
     
     • 입력 크기 n이 커질수록 수행시간도 증가 -> 입력 크기 n의 함수 f(n)으로 표현
       
     • 입력 데이터의 상태에 종속적
       
       
  2. 입력 데이터의 상태
     
     • 최악 수행시간을 참고
       
     • 평균 수행시간은 현실적으로 모든 경우에 대한 데이터를 구하기 쉽지 않음
       
     • 최선 수행시간은 이외 데이터들의 범위가 예상 불가하기에 우열을 가리기 모호함 (최악의 경우 다른값은 무조건 그 이하)
       
       

점근성능

• 입력 크기가 충분히 커짐에 따라 함숫값에 가장 큰 영향을 미치는 차수를 찾음
  
• 수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
  
• 수행시간의 정확한 값이 아닌 어림값
  
• 수행시간의 증가 추세를 파악하는 것이 쉬움
  

• 알고리즘 간의 우열을 따질 때 유용
  
  

• 연산 시간의 크기 관계
  
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^)
    
    
• 알고리즘의 시간 복잡도를 구하려면 (이론)
  
  • 기본 연산의 수행 횟수의 합 f(n)을 구한 후
    
  • f(n) = O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾음
    
    
• 실용적인 접근 방법
  
  • 알고리즘의 모든 문장이 아닌 ‘루프의 반복 횟수’만을 조사하여 최고 차수를 시간 복잡도로 취함
    
  • O(최고차수)