정말 몇일동안 고민해도 몰라서요~ 피보나치 수열 시간복잡도에 관해서 설명좀 부탁드려도 될까요?? ㅠㅠ
글쓴이: kingnns / 작성시간: 수, 2011/03/16 - 11:18오후
자료구조 c언어로 공부하고 있는데요~
순환 부분에서 팩토리얼, 하노이까진 이해하겠는데
피보나치의 반복 구조까지도 이해 했는데 (O(n))
피보나치의 재귀호출 할 때의 시간 복잡도 어떻게 구해야 할까요??
책도 다 뒤져보고 인터넷에도 다 찾아봤는데 답이 n^2 이라는 것과 2^(n/2) 로 나뉘는데
어느것 하나 이해할 수가 없어서 이렇게 질문 합니다 ㅠㅠ
int fib(int n)
{
if (n<=1) return n;
else
return fib(n-1) + fib(n-2);
}
가 소스코드인데 이것에 대한 시간복잡도와 빅오표기법 O(n)은 어떻게 구해야 할까요 ㅠㅠ
보통 설명되어 있는게
T(n) > 2*T(n-2) +1 이었나??
이 이후로는 이해가 안가요 ㅠㅠㅠㅠ
몇날몇일 이 개념 붙잡고 공부하는데 이제 겨우 하노이탑 이해했어요 ㅠㅠ
Forums:
구현마다 다릅니다.
그냥 재귀호출을 안쓴다면 O(n)이면 충분 할 듯 하네요. 재귀호출 버전의 경우 O(2^(n/2)) 이 됩니다. 잘 생각 해 보면 T(n) > 2*T(n-2) +1 식에서 충분히 구할 수 있습니다. T(n)+1 > 2(T(n-2)+1) 과 고등학교 수학1에서 나오면 등비급수를 사용하면 충분합니다.
...
(헛소리 썼다가 깨닫고 자삭)
다른 얘기지만
왜 recursive가르칠때 피보나치부터 가르치는 걸까요?
사람들이 recursive의 아름다움을 깨닫지 못하는게 약간 슬퍼집니다.
...
공학수학 같은 데서 배우는 differential/difference equation 푸는 법을 조금 응용하시면 됩니다.
T(n) = T(n-1) + T(n-2) + 1 꼴인 셈인데, T(n)은 homogeneous solution + particular solution입니다. 전자는 +1을 제외한 방정식의 근이며, 후자는 뒤에 +1이 붙어 있으니 상수로 추정할 수 있습니다.
H(n) = H(n-1) + H(n-2)는 second order이므로 H(n) = p^n으로 가정할 때, 이 식을 만족시키는 두 개의 상수 p가 존재합니다. p^2 - p - 1 = 0의 두 근이지요. 각각을 q, r이라고 하면, H(n) = c1 * q^n + c2 * r^n 꼴로 표현됩니다.
따라서 T(n) = c1 * q^n + c2 * r^n + c 꼴로 표현되는데, O(n)은 가장 dominant한 항에 의존하니까 q = ( 1 + 루트5) / 2 에 대해 O(q^n)이 됩니다.
덧. Recursion을 이해하는 건 code를 이해한다는 의미가 아닌 것 같습니다. 문제 해결 방식을 이해하는 것이죠. 코드는 작은 부분이라고 봅니다.. 일례로 고등학교에서 mathematical induction(수학적 귀납법)에 기반을 둔 증명을 배우지요. 증명하라고 나오는 것들은 흔히 까다롭습니다. 그런데, 그 명제 p(n)이 마치 증명된 양 가정해 버리고 p(n+1)을 p(n)을 이용해 풀면, 다시 말해, 둘 사이의 상대적으로 단순한 관계만 찾아주면, p(1)을 증명하는 것만으로 까다로워보였던 p(n)의 증명이 자연스레 끝나 버립니다. Recursion이란 사고 방식의 강력함을 나타내는 하나의 예일 텐데요, recursion을 배운다는 건, 이런 강력한 문제풀이 전략을 체득한다는 데 중점이 있는 게 아닐까요?
댓글 달기