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

재귀 알고리즘의 시간 복잡도는 [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

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)

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

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

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

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

시간 복잡도는

재귀 트리의 규칙은 다음과 같이 얻을 수 있습니다.

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

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

또 다른 예:

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

다음

은

요약하면 재귀 알고리즘의 복잡성을 해결하려면 다음 방법을 사용하세요.

f(n) = af(n/b) + d(n)

2. d(n) = cn ：

3. d(n)이 다른 상황인 경우 재귀 트리를 분석에 사용할 수 있습니다.

두 번째 경우부터 분할 정복 방법을 사용하여 원래 알고리즘을 개선하는 경우 새로운 계산 방법을 사용하여 a의 값을 줄이는 데 중점을 둡니다. ​

위 내용은 재귀 알고리즘의 시간 복잡도는 얼마입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!