자료구조 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 이었나??
이 이후로는 이해가 안가요 ㅠㅠㅠㅠ
몇날몇일 이 개념 붙잡고 공부하는데 이제 겨우 하노이탑 이해했어요 ㅠㅠ
