[알고리즘] 점화식의 점근적 분석 방법
많은 알고리즘은 큰 문제를 작은 문제로 쪼개서 해결하는 방법으로 해결할 수 있다. 이러한 문제 해결 방법을 Divide and Conquer (분할 후 정복) 이라고도 하는데, 이러한 구조 때문에 알고리즘의 시간 복잡도를 점화식의 꼴로 나타낼 수 있게 된다. 점화식이란 어떤 함수를 그 함수로 나타낸 식을 의미한다. 예를 들면 T(n) = T(n-1) + n 과 같이 T(n)에 대한 정의를 T(n-1)을 이용해 나타낸 경우가 점화식에 해당한다. 이러한 특성을 가진 알고리즘들은 재귀함수와도 연관이 깊다. 이제 시간복잡도가 점화식 꼴로 나타나는 경우 시간 복잡도를 계산하는 방법 3가지를 알아보겠다. 점화식의 점근적 분석 방법 1. 반복대치 첫 번째는 반복대치이다. 반복대치는 처음의 점화식을 계속 대입하면서 시..
알고리즘
2024. 2. 29. 18:52
