반복 대치 (1) 썸네일형 리스트형 [C언어] 점화식과 점근적 분석 방법(반복대치,추정후 증명, 마스터 정리) 쉽게 배우는 알고리즘 책을 참고했습니다. 안녕하세요!! 점화식 점화식이란? 어떤 함수를 자신과 똑같은 함수를 이용해서 나타내는 것입니다. 다시말해 재귀함수의 구조를 갖는 알고리즘만!! 점화식으로 표현할 수 있다 이말입니다. 재귀함수란? F(n) = n * F(n - 1) ; // 팩토리얼 F(n) = F(n - 1) + F(n - 2) ; // 피보나치 수 F(n) = F(n/2) + C ; //데이터를 두가지로 나누는 정렬! 등.. 자기자신을 호출하는 형식을 갖는 것은 재귀함수라고 표현할 수 있습니다. F(n) = n^2 + n + 1 이런 형식은 쉽게 시간 복잡도를 구할 수 있지만, 자기 자신을 갖는 점화식일 경우에는 점화식의 점근적 분석 방법을 통해서 F(n) = F(n-1)+ ...의 형태를 F(.. 이전 1 다음
