학습목표
- 알고리즘의 시간 복잡도와 공간 복잡도의 개념을 이해하고 그 차이점을 설명할 수
있다.
- 알고리즘에서 효율성의 개념을 이해하고, 주어진 코드 또는 알고리즘에 대하여 최선의 경우와 최악의 경우, 평균의 경우에서 효율성을 분석할 수 있다.
- Big-Oh, Big-Omega, Theta 표기법을 이용하여 알고리즘의 시간 복잡도를 점근적으로 표기하는 방법을 이해할 수 있다.
- 시간 복잡도의 점근적 표기법을 함수 그래프로 표현하고, 상한과 하한의 관계를 설명할 수 있다.
1. 알고리즘의 효율성 분석 개요
알고리즘의 효율성을 표현하는 방법
알고리즘의 효율성
- 수행 시간(시간 복잡도) 또는 사용되는 메모리 크기(공간 복잡도)
- 일반적으로는 시간 복잡도가 주로 사용
시간 복잡도
- 기본 연산의 횟수를 입력 크기에 대한 함수로 나타남
- 기본 연산 : 데이터 간 크기 비교, 데이터 읽기, 갱신, 숫자 계산과 같은 단순한 연산
- ex) 10장의 숫자 카드 중에서 최대 숫자 찾기
시간 복잡도 분석 방법
최악의 경우 분석
- 어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다 → 즉, 상한을 의미
평균의 경우 분석