피보나치 수열의 경우
이를 해결하기 위해 재귀적 방법과 비재귀적 방법을 사용할 수 있습니다.
문제를 해결하기 위해 다음 두 가지 방법을 사용하고 알고리즘의 시간 복잡도를 분석합니다.
를 입력할 때
를 입력할 때
가 맞을 때
가 맞다고 가정합니다.
이로써 알고리즘의 정확성이 입증되었습니다.
의 경우 각 문제는 두 개의 하위 문제로 나뉩니다. 각 분할마다 문제의 크기가 선형적으로 감소합니다.
각 노드에 대해 작업을 수행하는 각 노드의 해당 알고리즘의 시간 복잡도는 입니다.
이진 트리의 총 레벨 수는 대략적으로 다음과 같이 생각할 수 있습니다.
구체적인 분석은 다음과 같습니다:
For:
꼬리 상수 4는 4개의 상수 연산(비교 1회, 빼기 2회, 덧셈 1회)을 나타냅니다.
다음과 같이 대체할 수 있습니다.
하한에 대해 다음과 같이 말합니다.
우리는
다음을 얻을 수 있다고 생각합니다:
치환을 통해 다음을 얻을 수 있습니다:
따라서 상한에 대해 다음과 같이 말합니다.
요약하자면 이 알고리즘의 시간 복잡도
우선 A[0]과 A[1]에 값을 할당하려면 각각 두 가지 연산이 필요합니다.
루프 부분의 시간복잡도는 입니다.
그러니까
정리하자면, 반복적인 방법으로 피보나치를 푸는 시간복잡도는
원래 제 개인 블로그에 올렸던 글입니다. 방문을 환영합니다.