# Recurrence relations and Analysis (2/2)
---
**Contents**
**1️⃣** 점화식과 재귀 알고리즘 (Recurrence relations and recursive algorithms)
점화식의 분석 방법 (Method of analyzing recurrence relations)
**2️⃣**반복 대치 (Iterative substitution)
**3️⃣**추정 후 증명 (Guess and verify)
**4️⃣**마스터 정리 (Master theorem)
---
## **1️⃣** 점화식과 재귀 알고리즘
(Recurrence relations and recursive algorithms)
![Uploaded image](https://files.oaiusercontent.com/file-2UdjjjRc6hBYWjeyWB5LkoGR?se=2024-09-25T10%3A46%3A42Z&sp=r&sv=2024-08-04&sr=b&rscc=max-age%3D299%2C%20immutable%2C%20private&rscd=attachment%3B%20filename%3Dimage.png&sig=TPQHn6iweyWZQx3ybLtadTkxWizhW8BzXXlKtvNuTo4%3D align="left")
1. \*\*점화식(\*\*Recurrence relations)은 어떤 함수가 자신과 동일한 함수, 혹은 작은 변수로 표현될 때 그 관계를 나타내는 식이다. 즉, 문제를 작은 문제로 나누는 방식으로 정의된다.
* **기초 예제**: 피보나치 수열
```c
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(5)) # Output: 5
```
2. \*\*재귀 알고리즘(\*\*Recursive algorithms)은 자기 자신을 반복해서 호출하는 알고리즘으로, 점화식에 따라 알고리즘의 실행이 이루어진다.
점화식을 통해 재귀 알고리즘의 **수행시간**을 표현하고, 이를 통해 **시간복잡도**를 계산할 수 있게된다.
* **기초 예제**: 팩토리얼 계산
```c
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5)) # Output: 120
```
**단계 요약:**
1. **재귀 알고리즘**이 있다면, 그 알고리즘을 점화식으로 표현할 수 있다.
2. 이 점화식을 통해 알고리즘의 수행시간을 나타낸다.
3. 그리고 이를 바탕으로 **시간복잡도**를 계산할 수 있다.
이 과정은 복잡한 재귀 알고리즘의 성능을 분석하고, 얼마나 효율적인지 측정하는 데 매우 유용하다.
---
**점화식과 재귀알고리즘의 예**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727261284833/14415362-0670-44ad-9764-e26bf3cc954b.png align="center")
💡\*\*점화식의 예:\*\* 이 이미지에 나오는 점화식들은 각각 다른 형태의 재귀식을 보여주고 있다. **이러한 점화식을 통해 재귀 알고리즘의 복잡도를 분석**할 수 있으며, 각각의 경우에 따라 **수행시간이나 자원 사용량을 예측**할 수 있다. 이를 이해하는 것이 재귀 알고리즘과 시간복잡도 분석에 매우 중요하다. 간단히 살펴보자
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727261403152/8f0908d2-e999-4eeb-9f9a-492b33cbfb78.png align="center")
* 이 점화식은 현재 값 an이 이전 값 an−1의 3배라는 것을 의미한다. 즉, 이전 값의 3배씩 증가하는 패턴을 보인다는 뜻이다. 이 경우, 일반적인 계산식을 통해 이를 풀 수 있다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727261482885/3118a127-b268-4899-9e2c-cbd4ef1ddd31.png align="center")
* 이 점화식은 f(n)이 이전 값 f(n−1)에 n²을 곱하는 형태이다. 즉, 재귀적으로 이전 값을 기반으로 계산이 진행되며, 각 단계에서 2n²이라는 곱셈 연산이 추가된다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727261578774/43e073e8-5235-460a-8a56-0693a45736f6.png align="center")
* 이 점화식은 f(n)이 두 개의 이전 값, 즉 f(n−1)과 f(n-3)을 더한 결과로 정의된다. 이러한 점화식은 Fibonacci 수열과 유사한 구조를 가진다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727261625325/91796802-48b2-423d-b35c-5eb70b1afab9.png align="center")
* 이 점화식은 f(n)이f(n/2)에 1을 더한 값이다. 이는 문제의 크기가 절반으로 나뉘면서 계산이 진행되는 **로그 기반 재귀**의 형태로, 시간복잡도는 O(logn)에 가까운 경향을 보일 수 있다.
---
**💡재귀알고리즘의 예**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727262231936/19c16b4e-0908-4326-9758-fe9bf6542d95.png align="center")
* **팩토리얼 함수 이해하기**:
* **Base case**: n=1일 때, 1을 반환한다. 즉 `1! = 1`
* `1! = 1` "1의 팩토리얼은 1이다"라는 뜻이다. 팩토리얼(기호: !)은 자연수 n에 대해, n!을 n×(n−1)×(n−2)×...×1로 정의하는 연산이다. 즉, n부터 1까지의 모든 자연수를 곱한 값이라는 뜻이다.
하지만 **1의 팩토리얼**은 특별한 경우로 정의되어 있으며, **1!은 1**이다.
* 예시:
* 1!=1
* 2!=2×1=2
* 3!=3×2×1=6
따라서, **1! = 1**은 팩토리얼 연산에서 가장 기본적인 규칙 중 하나이다.
* **Recursive case**: 그 외의 경우에는, n!은 n × (n−1!)로 계산된다. 예를 들어, 3!을 구한다고 하면 3 × 2!입니다. 그리고 2!은 2 × 1!로 계산되고, 결국 1! = 1이기 때문에 계산이 끝난다.
ㅇ
* **재귀 호출의 의미**: 위에서 언급했듯이 재귀 함수는 자기 자신을 다시 호출하는 함수이다. 여기서 팩토리얼 함수는 n이 1이 될 때까지 계속해서 자기 자신을 호출하면서 n 값을 줄여나가고, 마지막에 도달하면 그 값을 하나씩 다시 곱하면서 결과를 계산다.
* **시간 복잡도 분석**:
* 팩토리얼에서는 f(n) = f(n−1)+1 이라는 점화식(Recurrence relations)을 따르며,현재 계산이 n - 1에 의존함을 보여준다. 결국 이 계산이 n번 늘어나므로, 시간 복잡도는 O(n)이다.
* 즉, 이 함수는 입력 값 n에 비례해서 실행 시간이 늘어나며, 이는 n번 재귀 호출을 통해 팩토리얼 값을 계산하게 되는 구조라고 할 수 있다.
---
### 점화식의 분석 방법
(Method of analyzing recurrence relations)
### **2️⃣**반복 대치 (Iterative substitution)
점화식의 분석 방법에서 **반복 대치**(Iterative Substitution)는 점화식을 풀어 **시간 복잡도**를 계산하는 데 유용한 기법 중 하나이다. 이를 통해 함수가 입력 크기 n에 따라 어떻게 변화하는지를 계산할 수 있게 된다. 시간 복잡도가 \*\*O(n)\*\*이나 \*\*O(n log n)\*\*인 경우는 반복 대치 기법을 통해 계산될 수 있다. O(n)먼저 살펴보자
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727264444954/b485c849-584c-42bf-9d2c-3893255cb69b.png align="center")
위의 식은, 어떤 함수가 자기 자신을 호출하는 **재귀 함수**의 시간 복잡도를 계산하는 방법을 보여주고 있다.
분석을 쉽게 설명하면:
1. **T(n) = T(n-1) + c** 이라는 것은, **n** 크기의 문제를 풀 때, **n-1** 크기의 문제를 해결하고, 그 외에 추가 작업으로 **c** 시간이 걸린다는 뜻이다. 여기서 **c**는 작은 상수 시간이다.
2. 이 식을 계속해서 펼쳐나가면,
* **T(n) = T(n-1) + c**
* **\= (T(n-2) + c) + c = T(n-2) + 2c**
* **\= (T(n-3) + c) + 2c = T(n-3) + 3c**
이런 식으로 반복되며, 결국 \*\*T(1)\*\*까지 도달하게 된다.
3. 그래서 마지막에 도출되는 결론은 **T(n) = c \* n**이 된다. 즉, 이 함수의 시간 복잡도는 **O(n)** 이다.
팩토리얼 함수와 비슷한 점은, 팩토리얼 함수도 재귀적으로 자기 자신을 호출하며, 그에 따른 시간 복잡도도 계산할 수 있다는 점이다. 팩토리얼의 경우, 매번 n에 대해 한 번씩 계산하기 때문에 O(n)의 시간이 소요된다. 이 분석 방식이 재귀 함수에 대한 일반적인 시간 복잡도 분석 방법이라 팩토리얼을 포함한 여러 재귀 함수의 복잡도를 이해하는 데 도움이 된다.
---
Q: 왜 T(n) = c \* n가 O(n)이 나요? O가 빅-오 함수표기법과 연관있는건가요?
A: 그렇다.빅-오 표기법은 **알고리즘의 성능**을 \*\*입력 크기(n)\*\*에 따라 **가장 빠르게 증가하는 항**을 기준으로 **최악의 경우의 시간 복잡도**를 나타내는 방법이다. 간단히 말해, 입력이 커질수록 알고리즘이 얼마나 오래 걸리는지를 나타내는 것이다.
**왜 T(n) = c \* n이 O(n)인가?**
1. \*\*T(n) = c *n에서* ***c****는 상수이다. 즉, 알고리즘이 n 크기의 입력에 대해 c* n 시간만큼 걸린다는 의미이다. 이때 **c**는 입력 크기에 영향을 받지 않고 일정한 값이다. 중요한 것은 **n**이 커질 때, 시간 복잡도는 **n**에 비례한다는 것이다.
2. **빅-오 표기법**에서는 **상수 값은 무시**한다. 즉, 상수 **c**가 무엇이든, 우리가 궁금한 것은 \*\*입력 크기(n)\*\*에 따라 시간이 얼마나 빨리 증가하느냐이다. 여기서 시간이 **n**에 비례하여 증가하므로, 이를 \*\*O(n)\*\*이라고 표현하는 것이다.
**빅-오 표기법을 사용하는 이유**
알고리즘의 성능을 비교할 때, \*\*입력 크기(n)\*\*에 따라 성능이 얼마나 나빠지는지, 어떤 알고리즘이 더 효율적인지를 판단할 때 사용한다. \*\*상수 항(c)\*\*는 알고리즘 성능 비교에 큰 의미가 없기 때문에, 가장 중요한 것은 **n에 대한 의존성**이다.
따라서 \*\*T(n) = c *n이라는 결과가 나왔을 때, 상수* ***c****는 중요하지 않으며,* ***n에 비례해서 시간이 걸리기 때문에*** \*O(n) 빅-오 표기법\*\*으로 시간 복잡도를 표현한다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727264865485/ab300136-da1b-4eb5-8dde-2717ea42c67a.png align="center")