학습목표

• 알고리즘의 시간 복잡도와 공간 복잡도의 개념을 이해하고 그 차이점을 설명할 수 있다.
• 알고리즘에서 효율성의 개념을 이해하고, 주어진 코드 또는 알고리즘에 대하여 최선의 경우와 최악의 경우, 평균의 경우에서 효율성을 분석할 수 있다.
• Big-Oh, Big-Omega, Theta 표기법을 이용하여 알고리즘의 시간 복잡도를 점근적으로 표기하는 방법을 이해할 수 있다.
• 시간 복잡도의 점근적 표기법을 함수 그래프로 표현하고, 상한과 하한의 관계를 설명할 수 있다.

1. 알고리즘의 효율성 분석 개요

알고리즘의 효율성을 표현하는 방법

알고리즘의 효율성

• 수행 시간(시간 복잡도) 또는 사용되는 메모리 크기(공간 복잡도)
• 일반적으로는 시간 복잡도가 주로 사용

시간 복잡도

• 기본 연산의 횟수를 입력 크기에 대한 함수로 나타남
• 기본 연산 : 데이터 간 크기 비교, 데이터 읽기, 갱신, 숫자 계산과 같은 단순한 연산
• ex) 10장의 숫자 카드 중에서 최대 숫자 찾기
  • 9번임, n장의 카드라면 n-1번

시간 복잡도 분석 방법

최악의 경우 분석

• 어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다 → 즉, 상한을 의미

평균의 경우 분석

• 알고리즘의 수행 시간의 평균을 분석함