피보나치 서열의 계산 복잡성
https://stackoverflow.com/questions/360748
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 big-o 표기법을 이해하지만 많은 기능에 대해 그것을 계산하는 방법을 모르겠습니다. 특히, 나는 Fibonacci 시퀀스의 순진한 버전의 계산 복잡성을 알아 내려고 노력했다.
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci 서열의 계산 복잡성은 무엇이며 어떻게 계산됩니까?
해결책
계산할 시간 기능을 모델링합니다 Fib(n) 계산 시간의 합으로 Fib(n-1) 또한 계산할 시간 Fib(n-2) 또한 함께 추가 할 시간 (O(1)). 이것은 동일한 평가를 반복적으로 평가한다고 가정합니다 Fib(n) 동시에 시간을 내십시오. 즉, 메모리가 사용되지 않습니다.
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
이 재발 관계 (예 : 생성 함수 사용)를 해결하면 답으로 끝납니다.
또는 재귀 트리를 그릴 수 있습니다. n 그리고이 기능이 비대칭 적으로 직관적으로 알아냅니다 O(2n). 그런 다음 유도로 추측을 증명할 수 있습니다.
베이스: n = 1 분명합니다
추정하다 T(n-1) = O(2n-1), 그러므로
T(n) = T(n-1) + T(n-2) + O(1) 그것은 동일합니다
T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)
그러나 의견에서 언급 한 바와 같이, 이것은 단단한 경계가 아닙니다. 이 기능에 대한 흥미로운 사실은 t (n)이 무증상 적으로 똑같다 값으로 Fib(n) 둘 다 정의되므로
f(n) = f(n-1) + f(n-2).
재귀 트리의 잎은 항상 반환됩니다. 1. Fib(n) 재귀 트리의 잎에 의해 반환 된 모든 값의 합은 잎의 수와 동일합니다. 각 잎은 계산하는 데 O (1)가 필요하기 때문에 T(n) 와 동등하다 Fib(n) x O(1). 결과적으로,이 기능의 단단한 경계는 Fibonacci 시퀀스 자체입니다 (~θ(1.6n)). 위에서 언급 한 것처럼 생성 함수를 사용 하여이 단단한 바운드를 찾을 수 있습니다.
다른 팁
얼마나 많은 진술을 실행 해야하는지 스스로에게 물어보십시오. F(n) 완료합니다.
을 위한 F(1), 정답은 1 (조건부의 첫 번째 부분).
을 위한 F(n), 정답은 F(n-1) + F(n-2).
그렇다면 이러한 규칙을 충족시키는 기능은 무엇입니까? 시도해보십시오N (A> 1) :
ㅏN == a(N-1) + a(N-2)
a(N-2):
ㅏ2 == a + 1
해결하십시오 a 그리고 당신은 얻습니다 (1+sqrt(5))/2 = 1.6180339887, 그렇지 않으면 그렇지 않으면 황금 비율.
기하 급수 시간이 걸립니다.
이것에 대한 아주 좋은 토론이 있습니다 MIT에서 구체적인 문제. 5 페이지에서 추가로 추가가 하나의 계산 단위를 취한다고 가정하면 FIB (N)를 계산하는 데 필요한 시간은 FIB (N)의 결과와 매우 밀접한 관련이 있다고 지적합니다.
결과적으로 Fibonacci 시리즈의 매우 근사치로 직접 건너 뛸 수 있습니다.
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
그러므로 순진한 알고리즘의 최악의 성능은
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
추신 :에 대한 토론이 있습니다 nth fibonacci 번호의 폐쇄 형태 표현 더 많은 정보를 원한다면 Wikipedia에서.
나는 pgaur와 rickerbh에 동의합니다. 재귀 피보나치의 복잡성은 O (2^n)입니다.
나는 다소 단순한 것으로 같은 결론에 도달했지만 여전히 유효한 추론을 믿는다.
첫째, NTH Fibonacci 번호를 계산할 때 재귀 Fibonacci 함수 (지금부터)가 몇 번이나 호출되는지 알아내는 것이 전부입니다. 시퀀스 0에서 n에서 숫자 당 한 번 호출되면 O (n)이 있습니다. 각 숫자에 대해 n 번으로 호출되면 o (n*n) 또는 o (n^2), 등등.
따라서, f ()가 숫자 n을 요구할 때, 우리가 0에 접근함에 따라 0과 n-1 사이의 주어진 숫자에 대해 f ()의 수가 호출된다.
첫인상으로, 우리가 시각적 방식으로 놓으면 시간당 단위를 뽑는 것이 주어진 숫자를 요구하는 것 같습니다. ). 이 같은:
n *
n-1 **
n-2 ****
...
2 ***********
1 ******************
0 ***************************
이제 문제는 N이 자라 면서이 피라미드의 기초가 얼마나 빨리 확대됩니까?
예를 들어 F (6)과 같은 실제 사례를 봅시다
F(6) * <-- only once
F(5) * <-- only once too
F(4) **
F(3) ****
F(2) ********
F(1) **************** <-- 16
F(0) ******************************** <-- 32
우리는 f (0)이 32 배,이 샘플 케이스의 경우 2^(n-1)이라고 불립니다.
이제 우리는 F (x)가 몇 번이나 호출되는지 알고 싶습니다. F (0)이라는 횟수가 그 일부임을 알 수 있습니다.
우리가 모든 *의 모든 것을 f (6)에서 f (2) 라인으로 f (1) 선으로 정신적으로 옮기면 f (1) 및 f (0) 라인이 이제 길이가 같음을 알 수 있습니다. 즉, N = 6이 2x32 = 64 = 2^6 인 경우 총 시간 F ()가 호출됩니다.
이제 복잡성 측면에서 :
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
당신은 그것을 확장하고 방문을 가질 수 있습니다
T(n) = T(n-1) + T(n-2) <
T(n-1) + T(n-1)
= 2*T(n-1)
= 2*2*T(n-2)
= 2*2*2*T(n-3)
....
= 2^i*T(n-i)
...
==> O(2^n)
아래쪽 끝에 제한되어 있습니다 2^(n/2) 그리고 상단에서 2^n (다른 의견에서 언급 된 바와 같이). 그리고 그 재귀 구현의 흥미로운 사실은 그것이 FIB (N) 자체의 단단한 점근 경계를 가지고 있다는 것입니다. 이러한 사실을 요약 할 수 있습니다.
T(n) = Ω(2^(n/2)) (lower bound)
T(n) = O(2^n) (upper bound)
T(n) = Θ(Fib(n)) (tight bound)
단단한 바운드는 ITS를 사용하여 추가로 줄일 수 있습니다 닫힌 양식 당신이 좋아한다면.
증거 답변은 좋지만, 나는 항상 자신을 확신시키기 위해 항상 손으로 몇 가지 반복을해야합니다. 그래서 나는 화이트 보드에 작은 호출 나무를 꺼내고 노드를 세기 시작했습니다. 카운트를 전체 노드, 잎 노드 및 내부 노드로 나눕니다. 여기에 내가 얻은 것은 다음과 같습니다.
IN | OUT | TOT | LEAF | INT
1 | 1 | 1 | 1 | 0
2 | 1 | 1 | 1 | 0
3 | 2 | 3 | 2 | 1
4 | 3 | 5 | 3 | 2
5 | 5 | 9 | 5 | 4
6 | 8 | 15 | 8 | 7
7 | 13 | 25 | 13 | 12
8 | 21 | 41 | 21 | 20
9 | 34 | 67 | 34 | 33
10 | 55 | 109 | 55 | 54
즉시 도약하는 것은 잎 노드의 수가 fib(n). 몇 가지 더 많은 반복이 필요한 것은 내부 노드의 수가 fib(n) - 1. 따라서 총 노드 수는 다음과 같습니다 2 * fib(n) - 1.
계산 복잡성을 분류 할 때 계수를 삭제하기 때문에 최종 답은 다음과 같습니다. θ(fib(n)).
재귀 알고리즘의 시간 복잡성은 재귀 트리를 그리면 더 잘 추정 될 수 있습니다.이 경우 리포지션 트리를 그리는 재발 관계는 t (n) = t (n-1)+t (n-2)+O (1)입니다. 각 단계는 o (1)를 의미하는 시간을 의미합니다. 만약에 Block.cursion 트리는 모양이 될 것입니다
n
(n-1) (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on
여기서 위의 나무의 각 레벨이 I로 표시된다고 가정합니다.
i
0 n
1 (n-1) (n-2)
2 (n-2) (n-3) (n-3) (n-4)
3 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)
I의 특정 값에서 나무가 끝나고, 그 경우는 ni = 1이 될 때이므로 i = n-1이므로 나무의 높이가 N-1임을 의미합니다. 이제 트리의 각 N 층에 대해 얼마나 많은 작업이 수행되는지 보자.
2^0=1 n
2^1=2 (n-1) (n-2)
2^2=4 (n-2) (n-3) (n-3) (n-4)
2^3=8 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6) ..so on
2^i for ith level
i = n-1은 각 레벨에서 수행 된 나무 작업의 높이이므로
i work
1 2^1
2 2^2
3 2^3..so on
따라서 완료된 총 작업은 각 레벨에서 수행 된 작업의 합계가되므로 I = N-1 이후 2^0+2^1+2^2^3 ...+2^(N-1)가됩니다. 기하학적 시리즈 로이 합계는 2^n이므로 여기서 총 시간 복잡성은 다음과 같습니다. O (2^N)
글쎄, 나에 따르면 그것에 따르면 O(2^n) 이 기능에서와 마찬가지로 재귀만이 상당한 시간 (분열 및 정복)이 걸립니다. 우리는 위의 기능이 레벨에 도달 할 때 잎이 접근 할 때까지 나무에서 계속 될 것임을 알 수 있습니다. F(n-(n-1)) 즉 F(1). 따라서 여기에서 우리가 각 나무 깊이에서 발생하는 시간 복잡성을 낮추면 요약 시리즈는 다음과 같습니다.
1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1
그것은 순서입니다 2^n [ O(2^n) ].
http://www.ics.uci.edu/~eppstein/161/960109.html
시간 (n) = 3f (n) -2
Fibonacci의 순진한 재귀 버전은 계산의 반복으로 인해 설계별로 지수됩니다.
루트에서 컴퓨팅 중입니다.
F (n)은 F (N-1) 및 F (N-2)에 따라 다릅니다.
F (n-1)는 다시 f (n-2)에 의존하고 f (n-3)
F (n-2)는 다시 f (n-3)에 의존하고 f (n-4)
그런 다음 계산에 많은 데이터를 낭비하는 각 레벨 2 재귀 호출에있어 시간 함수가 다음과 같습니다.
t (n) = t (n-1) + t (n-2) + c, c 상수와 함께
t (n-1) = t (n-2) + t (n-3)> t (n-2) 그런 다음
t (n)> 2*t (n-2)
...
t (n)> 2^(n/2) * t (1) = o (2^(n/2))
이것은 분석의 목적을 위해 충분해야한다는 하한 일 뿐이지 만 실시간 함수는 동일한 fibonacci 공식과 닫힌 양식 황금 비율의 지수로 알려져 있습니다.
또한 다음과 같은 동적 프로그래밍을 사용하여 최적화 된 Fibonacci 버전을 찾을 수 있습니다.
static int fib(int n)
{
/* memory */
int f[] = new int[n+1];
int i;
/* Init */
f[0] = 0;
f[1] = 1;
/* Fill */
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
그것은 최적화되어 있으며 만 수행합니다 N 단계이지만 지수입니다.
비용 함수는 입력 크기에서 문제를 해결하기위한 단계 수로 정의됩니다. 동적 버전의 Fibonacci를 볼 때 (N 테이블을 계산하는 단계) 또는 숫자가 프라임인지 알기위한 가장 쉬운 알고리즘 (sqrt (n) 숫자의 유효한 제수를 분석하려면). 이러한 알고리즘이 있다고 생각할 수도 있습니다 에) 또는 o (sqrt (n)) 그러나 이것은 다음과 같은 이유로 사실이 아닙니다. 알고리즘에 대한 입력은 숫자입니다. N, 이진 표기법을 사용하여 정수의 입력 크기 N ~이다 log2 (n) 그런 다음 변수 변경을 수행합니다
m = log2(n) // your real input size
입력 크기의 함수로 단계 수를 찾으십시오.
m = log2(n)
2^m = 2^log2(n) = n
그런 다음 입력 크기의 함수로서 알고리즘 비용은 다음과 같습니다.
T(m) = n steps = 2^m steps
이것이 바로 비용이 지수 인 이유입니다.
