알고리즘의 분석

• 알고리즘의 자원(resource)사용량 을 분석
• 자원이란 실행 시간, 메모리, 저장장치, 통신 등
• 이 글에서는 실행시간의 분석에 대해서 다룬다

시간복잡도(time complexity)

• 실행시간은 실행환경에 따라 달라진다

  • 하드웨어, 운영체제, 언어, 컴파일러 등

• 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트

• 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현한다

• 데이터의 크기가 같더라도 실제 데이터에 따라서 달라진다

  • 최악의 경우 시간복잡도(worst-case analysis)
  • 평균 시간복잡도 (average-case analysis)

점근적(Asymptotic) 분석

• 점근적 표기법을 사용

  • 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법
  • Θ-표기, Ο-표기 등을 사용

• 유일한 분석법도 아니고 가장 좋은 분석법도 아니다

  • 다만 (상대적으로) 가장 간단하다
  • 알고리즘의 실행환경에 비의존적이다
  • 그래서 가장 광범위하게 사용된다

점근적 분석의 예: 선형 시간복잡도

입력으로 n개의 데이터가 저장된 배열 data가 주어지고,
그 합을 구하여 반환한다

선형 시간복잡도를 가진다고 말하고 O(n)이라고 표기한다.

선형 시간복잡도: 순차탐색

배열 data에 정수 target이 있는지 검색한다.

최악의 경우 시간복잡도는 O(n)이다.

배열 x에 중복된 원소가 있는지 검사하는 함수이다.

최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는 n(n-1)/2이다.
최악의 경우 시간복잡도는 O(n2)으로 나타낸다

점근적 표기법

• 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법
• 최고차항의 차수만으로 표시한다
• 따라서 가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다