3주차 - 점화식과 점근적 복잡도의 분석 및 정렬

점화식과 점근적 복잡도의 분석

점화식

정의

• 어떤 함수를 자기보다 더 작은 변수에 대한 함수(재귀 함수)와의 관계로 표현한 것

• 점화식: \(T(n) = 2T(n/2) + 오버헤드\)¹

• 크기가 n인 병합 정렬 시간은 크기 n/2의 병합 정렬을 2번 실행하는 시간에 나머지 오버헤드를 합친 시간임

점화식의 점근적 분석 방법

반복 대치

• 더 작은 문제에 대한 함수를 계속 반복하면서 대치하는 방법

실행 과정

이진 검색

• 배열에 저장된 자료를 검색하기 위해 자료의 중간 위치와 반복비교를 통해 자료를 찾음
• 비교 연산 후 다음 비교 대상 자료는 현재 자료의 1/2임
  • 자료 개수가 n일 경우, n/2, n/4, n/8…..
  • 자료 개수가 1000개인 경우 \(log2^{1000}\)≒10번 내에 자료 검색이 가능함

추정 후 증명

• 결론을 추정 후 수학적 귀납법을 이용해 증명하는 방법

마스터 정리

• 형식에 맞는 점화식의 복잡도를 바로 알 수 있음

1. 오버헤드 : 특정 기능을 수행하기 위해 필요한 시간과 메모리등의 자원 ↩