gyeo-ri.com

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다. 점화식 명시적으로 자기 호출을 사용하지 않더라도 그 속에서 자신(n)과 똑같지만 크기가 다른(n-1) 문제를 발견할 수 있는 경우 재귀적 성질을 포함하는 알고리즘의 복잡도는 점화식을 이용하여 접근이 가능함 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 점화식의 점근적 복잡도를 구하는 방법 반복 대치 : T(n)의 식을 T(1)이 될 때 까지 반복하여 치환함 추정 후 증명 : 귀납적으로 가설을 설정, 가설을 만족함을 증명 시간 복잡도(빅오표기법 등)의 증명 과정 마스터 정리 : 특정한 모양을 가진 재귀식에 대해 바로 결과를 알 수 있는 정리 T(n) = aT(n/b) + f..