빙글빙글 돌아가는 맷돌

점화식 -어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 -자기호출을 사용하는 함수의 복잡도를 구하는데 유용하게 쓰임 점화식의 점근적 분석 방법 -반복대치 -추정 후 증명 -마스터 정리 1) 반복 대치 (예1) n! factorial(n) { if(n=1) return 1; return n*factorial(n-1); } (예1 해답) T(n)=T(n-1)+c T(1)≤c T(n)=T(n-1)+c=T(n-2)+2c=...=T(1)+(n-1)c=cn ∴T(n)=O(n) 2) 추정 후 증명 (문제) T (n) = 2T (n/2) + n 추정: T(n) = O(nlogn), 즉 T(n) ≤ cn log n를 만족하는 c가 존재한다 경계조건: T(2) ≤ c2log2를 만족하는 c가 존재한..

알고리즘이란 -문제 해결 절차를 체계적으로 기술한 것 -문제 요구 조건 : 1) 입,출력 명시 2) 입력으로 출력 만드는 과정 알고리즘 분석 -해당 알고리즘이 자원(소요시간, 메모리 등)을 얼마나 소모하는지 -시간 분석 : 1) 최악/평균의 경우 2) 어느정도 입력에 어느 정도 시간이 필요한 지 짐작 3)입력 크기 대해 시간이 어떤 비율로 소요되는지로 표현 재귀 = 자기호출, 어떤 문제 안에 크기만 다를 뿐 같은 성격의 작은 문제들이 포함되어 있는 것 = factorial, 점화식 점근석 알고리즘 분석 -크기가 작은 문제는 알고리즘 효율성이 중요하지 않음 -크기가 충분히 큰 문제는 알고리즘 효율성 중요함 -입력의 크기가 춤분히 큰 경우에 대한 분석 - Ο, Ω, Θ, ω, ο 표기법 1) O( g(n) ..