피보나치 수열

[CS스터디]220707 자료구조 - 3

BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요. 한쪽으로 몰리는 경우(계속해서 작은 수가 들어오는 경우, 계속해서 큰 수가 들어오는 경우)가 최악의 경우 평균적으로는 O(logN)인 시간 복잡도가 이 경우엔 O(N)으로 증가함! 피보나치 수열을 코드로 구현하는 방법에 대해서 설명해주세요. 재귀 or 동적 계획법(탑다운, 바텀업 방식이 있음) 재귀 단순한 재귀로 구현할 경우, 시간 복잡도가 너무 크게 나올 수 있기 때문에 동적 계획법을 활용하여 구현하는게 좋음 ! 동적 계획법 Top-Down 말 그대로 위에서 아래로 진행하면서 답을 구하는 방식, 흔히 재귀 호출을 이용해 구현. 100번째 피보나치 수를 찾기 위해 99번째, 98번째 수를 찾고, 그들을 찾기 위해 97번쨰, 96번째 수를 찾는..