[알고리즘] Efficiency & Analysis of Algorithms

알고리즘의 분석

• 시간복잡도 분석: 입력 크기에 따라 단위 연산이 몇 번 수행되는지 결정하는 절차
  • 최선의 경우 분석
    • 입력 크기와 입력 값 모두에 종속
    • 단위 연산이 수행되는 횟수가 최소인 경우 선택
  • 최악의 경우 분석
    • 입력 크기와 입력 값 모두에 종속
    • 단위 연산이 수행되는 횟수가 최대인 경우 선택
  • 평균의 경우 분석 (잘 쓰지 않음)
    • 입력 크기와 입력 값 모두에 종속
    • 모든 입력에 대해서 단위 연산이 수행되는 기대치
    • 각 입력에 대해서 확률 할당 가능
    • 일반적으로 최악의 경우보다 계산이 복잡

복잡도 표기법

• 점근적 표기: 입력 크기에 따라 소요 시간이 달라지므로, 복잡도를 간단히 표현하고자 사용
• Big-O 표기법: g(n)의 상한선을 설정하여 복잡도를 도출하는 방법
  
• Big-omega 표기법: g(n)의 하한선을 설정하여 복잡도를 도출하는 방법 (최악)
  

• Big-theta 표기법: Big-O와 Big-omega 표기법이 같은 경우에 사용