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)
**점화식(**Recurrence relations)은 어떤 함수가 자신과 동일한 함수, 혹은 작은 변수로 표현될 때 그 관계를 나타내는 식이다. 즉, 문제를 작은 문제로 나누는 방식으로 정의된다.
- 기초 예제: 피보나치 수열
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(5)) # Output: 5
**재귀 알고리즘(**Recursive algorithms)은 자기 자신을 반복해서 호출하는 알고리즘으로, 점화식에 따라 알고리즘의 실행이 이루어진다.
점화식을 통해 재귀 알고리즘의 수행시간을 표현하고, 이를 통해 시간복잡도를 계산할 수 있게된다.
기초 예제: 팩토리얼 계산
def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(5)) # Output: 120
단계 요약:
재귀 알고리즘이 있다면, 그 알고리즘을 점화식으로 표현할 수 있다.
이 점화식을 통해 알고리즘의 수행시간을 나타낸다.
그리고 이를 바탕으로 시간복잡도를 계산할 수 있다.
이 과정은 복잡한 재귀 알고리즘의 성능을 분석하고, 얼마나 효율적인지 측정하는 데 매우 유용하다.
점화식과 재귀알고리즘의 예
💡**점화식의 예:** 이 이미지에 나오는 점화식들은 각각 다른 형태의 재귀식을 보여주고 있다. 이러한 점화식을 통해 재귀 알고리즘의 복잡도를 분석할 수 있으며, 각각의 경우에 따라 수행시간이나 자원 사용량을 예측할 수 있다. 이를 이해하는 것이 재귀 알고리즘과 시간복잡도 분석에 매우 중요하다. 간단히 살펴보자
- 이 점화식은 현재 값 an이 이전 값 an−1의 3배라는 것을 의미한다. 즉, 이전 값의 3배씩 증가하는 패턴을 보인다는 뜻이다. 이 경우, 일반적인 계산식을 통해 이를 풀 수 있다.
- 이 점화식은 f(n)이 이전 값 f(n−1)에 n²을 곱하는 형태이다. 즉, 재귀적으로 이전 값을 기반으로 계산이 진행되며, 각 단계에서 2n²이라는 곱셈 연산이 추가된다.
- 이 점화식은 f(n)이 두 개의 이전 값, 즉 f(n−1)과 f(n-3)을 더한 결과로 정의된다. 이러한 점화식은 Fibonacci 수열과 유사한 구조를 가진다.
- 이 점화식은 f(n)이f(n/2)에 1을 더한 값이다. 이는 문제의 크기가 절반으로 나뉘면서 계산이 진행되는 로그 기반 재귀의 형태로, 시간복잡도는 O(logn)에 가까운 경향을 보일 수 있다.
💡재귀알고리즘의 예
팩토리얼 함수 이해하기:
Base case: n=1일 때, 1을 반환한다. 즉
1! = 11! = 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)먼저 살펴보자
위의 식은, 어떤 함수가 자기 자신을 호출하는 재귀 함수의 시간 복잡도를 계산하는 방법을 보여주고 있다.
분석을 쉽게 설명하면:
T(n) = T(n-1) + c 이라는 것은, n 크기의 문제를 풀 때, n-1 크기의 문제를 해결하고, 그 외에 추가 작업으로 c 시간이 걸린다는 뜻이다. 여기서 c는 작은 상수 시간이다.
이 식을 계속해서 펼쳐나가면,
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)**까지 도달하게 된다.
- 그래서 마지막에 도출되는 결론은 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)인가?
**T(n) = c n에서 c*는 상수이다. 즉, 알고리즘이 n 크기의 입력에 대해 c n 시간만큼 걸린다는 의미이다. 이때 c는 입력 크기에 영향을 받지 않고 일정한 값이다. 중요한 것은 n이 커질 때, 시간 복잡도는 *n에 비례한다는 것이다.
빅-오 표기법에서는 상수 값은 무시한다. 즉, 상수 c가 무엇이든, 우리가 궁금한 것은 **입력 크기(n)**에 따라 시간이 얼마나 빨리 증가하느냐이다. 여기서 시간이 n에 비례하여 증가하므로, 이를 **O(n)**이라고 표현하는 것이다.
빅-오 표기법을 사용하는 이유
알고리즘의 성능을 비교할 때, **입력 크기(n)**에 따라 성능이 얼마나 나빠지는지, 어떤 알고리즘이 더 효율적인지를 판단할 때 사용한다. **상수 항(c)**는 알고리즘 성능 비교에 큰 의미가 없기 때문에, 가장 중요한 것은 n에 대한 의존성이다.
따라서 **T(n) = c n이라는 결과가 나왔을 때, 상수 c*는 중요하지 않으며, **n에 비례해서 시간이 걸리기 때문에** \O(n) 빅-오 표기법**으로 시간 복잡도를 표현한다.
