알고리즘 분석

시간복잡도 (Time Complexity) 분석

• 입력 크기의 함수로 일부 기본 연산이 수행되는 횟수를 결정하여 알고리즘의 효율을 분석한다.

 

표현 척도

• Input size (입력 크기) : 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수, 그래프에서는 정점과 간선의 수
• Basic operation (단위 연산) : 비교 (comparison), 지정 (assignment)

 

분석 방법의 종류

• Every-case time complexity analysis (모든 경우 분석)
  • T(n) : 알고리즘이 n 크기의 인스턴스에 대해 basic operation을 수행하는 횟수 (the number of times the algorithm does the basic operation for an instance of size n)
  • 입력 크기에만 종속
  • 입력 값과는 무관하게 결과 값은 항상 일정
  • ex) Add array members, Exchange sort, Matrix multiplication
• Worst-case time complexity analysis (최악의 경우 분석)
  • W(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 최대 횟수 (the maximum number of times the algorithm will ever do its basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최대인 경우 선택
  • ex) Sequential search
• Average-case time complexity analysis (평균의 경우 분석)
  • A(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 평균 횟수 (the average number of times the algorithm does the basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 모든 입력에 대해서 단위 연산이 수행되는 기대치 (평균)
  • 각 입력에 대해서 확률 할당 가능
  • 일반적으로 최악의 경우보다 계산이 복잡
  • ex) Sequential search
• Best-case time complexity analysis (최선의 경우 분석)
  • B(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 최소 횟수 (the minimum number of times the algorithm will ever do its basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최소인 경우 선택
  • ex) Sequential search