집 > 기사 > 백엔드 개발 > 재귀 알고리즘의 시간 복잡도는 얼마입니까?

재귀 알고리즘의 시간 복잡도는 얼마입니까?

angryTom원래의: 2019-10-24 10:53:1948581검색

재귀 알고리즘의 시간 복잡도는 [T(n)=o(f(n))]입니다. 이는 문제 크기 n이 증가함에 따라 알고리즘의 실행 시간 증가율이 증가율에 비례한다는 것을 의미합니다. 이는 알고리즘의 점근적 시간 복잡도라고 불리는 f(n) 입니다. 재귀 알고리즘의 시간 복잡도는 다음과 같습니다.

재귀 알고리즘의 시간 복잡도는 얼마입니까? f(n)이 n에 따라 어떻게 변하고 T(n)의 크기 순서를 결정하는지. 여기서 'o'는 크기 순서를 나타내고 알고리즘의 시간 복잡도를 제공하는 데 사용됩니다.

T(n)=o(f(n)) 문제 크기 n이 커질수록 알고리즘의 실행 시간 증가율은 f(n)의 증가율에 비례한다는 뜻입니다. 알고리즘 복잡도의 점근 시간. 그리고 우리는 일반적으로 최악의 시간 복잡도에 대해 논의합니다.

추천 과정: C 언어 튜토리얼

공간 복잡도:

알고리즘의 공간 복잡도는 실제 점유된 공간이 아니라 전체 알고리즘 공간에서 보조 공간 단위의 수를 계산한 것입니다. 문제 관계의 규모와는 아무 관련이 없습니다. 알고리즘의 공간 복잡도 S(n)은 알고리즘이 소비하는 공간의 크기 순서로 정의됩니다.

S(n)=o(f(n)) 알고리즘 실행에 필요한 보조 공간이 입력 데이터 n에 대해 상수인 경우 알고리즘 공간 복잡도 보조 공간을 o(1)이라고 합니다. 재귀 알고리즘의 공간 복잡도: 재귀 깊이 n*각 재귀에 필요한 보조 공간 각 재귀에 필요한 보조 공간이 일정하면 재귀 공간 복잡도는 o(n)입니다.

재귀 알고리즘의 시간 복잡도 계산 방정식은 재귀 방정식입니다.

재귀 트리를 도입하기 전에 예를 고려할 수 있습니다.

T(n) = 2T(n/2) + n2

2번 반복하여 다음을 얻을 수 있습니다.

T(n) = n2 + 2(2T(n/4) + (n/2) 2)

할 수 있습니다. 또한 계속 반복하면 완전한 확장을 얻을 수 있습니다.

T(n) = n2 + 2((n/2) 2 +
2((n/22)2 + 2((n/23) 2 +
2((n/24) 2 +…+2((n/2i) 2 +
2T(n/2i + 1)))…))))……(1)

그리고 n/2i+1 == 1이면 반복이 종료됩니다.

방정식 (1)의 괄호를 확장하면 다음을 얻을 수 있습니다.

T(n) = n2 + 2(n/2)2 +
22(n/22) 2 + … + 2i(n/2i)2 +
2i+1T(n/2i+1)

이것은 재귀 트리 방법으로 이어질 수 있는 트리 구조입니다.

(a)(b)(c)(d)는 그림에서 각각 재귀 트리 생성의 1번째, 2번째, 3번째, n번째 단계입니다. 각 노드에서 현재 사용 가능한 항목 n2는 유지되고 두 개의 재귀 항목 T(n/2)

+T(n/2)은 각각 두 개의 하위 노드에 할당됩니다.

그래프에 있는 모든 노드의 합은 다음과 같습니다.

[1 + 1/2 + (1/2)2 + (1/2)3 + … + (1/2)i] n2 = 2n2

시간 복잡도는

O(n2)

재귀 트리의 규칙은 다음과 같이 얻을 수 있습니다. 재귀 알고리즘의 시간 복잡도는 얼마입니까?

(1) 노드 각 레이어의 T(n) = kT(n / m) + f(n)의 f(n) 값입니다.

(2) 각 노드의 분기 수는 k입니다.

(3) 각 레이어의 오른쪽 측면 마커는 현재 레이어에 있는 모든 노드의 합을 나타냅니다.

또 다른 예:

T(n) = T(n/3) + T(2n/3) + n

재귀 트리는 아래와 같습니다.

값을 볼 수 있습니다. 각 레이어의 값은 모두 n이고 루트에서 리프 노드까지의 가장 긴 경로는 다음과 같습니다.

최종 재귀는 (2/3)kn == 1에서 멈추기 때문입니다. 그런 다음

재귀 알고리즘의 시간 복잡도는 얼마입니까? 은