Big-O 표기법을 이해하지만 많은 함수에 대해 계산 방법을 모르겠습니다. 특히, 피보나치 시퀀스의 순진한 버전의 계산 복잡성을 알아 내려고 노력했습니다.
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
피보나치 수열의 계산 복잡성은 무엇이며 어떻게 계산됩니까?
답변
당신은 계산에 시간 함수를 모델링 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). 결과적으로이 함수의 밀접한 결합은 피보나치 수열 자체 (~ )입니다. 위에서 언급했듯이 생성 함수를 사용 하여이 빡빡한 경계를 찾을 수 있습니다.θ(1.6n)
답변
F(n)완료 하기 위해 얼마나 많은 명령문을 실행해야하는지 스스로에게 물어보십시오 .
에 대한 F(1)답은 1(조건부의 첫 번째 부분)입니다.
에 대한 F(n)대답은 F(n-1) + F(n-2)입니다.
그렇다면이 규칙을 충족시키는 기능은 무엇입니까? n (a> 1)을 시도하십시오 .
a n == a (n-1) + a (n-2)
(n-2)로 나눕니다 .
a 2 == a + 1
에 대한 해결 a당신은 얻을 (1+sqrt(5))/2 = 1.6180339887그렇지 않으면로 알려진 황금 비율 .
따라서 지수 시간이 걸립니다.
답변
나는 pgaur와 rickerbh에 동의합니다. 재귀 피보나치의 복잡성은 O (2 ^ n)입니다.
나는 다소 단순한 방법으로 같은 결론에 도달했지만 여전히 타당한 추론을 믿는다.
먼저, N 번째 피보나치 수를 계산할 때 재귀 피보나치 함수 (여기부터 F ())가 몇 번이나 호출되는지 파악해야합니다. 순서 0에서 n까지 숫자 당 한 번 호출되면 O (n)이되고 각 숫자에 대해 n 번 호출되면 O (n * n) 또는 O (n ^ 2)가됩니다. 등등.
따라서 숫자 n에 대해 F ()를 호출하면 0에 접근함에 따라 0과 n-1 사이의 주어진 숫자에 대해 F ()가 호출 된 횟수가 증가합니다.
첫인상으로, 시각적으로 표현하면 주어진 숫자에 대해 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 ^ 5입니다.이 샘플의 경우 2 ^ (n-1)입니다.
이제 F (x)가 몇 번이나 호출되는지 알고 싶습니다. F (0)이 호출 된 횟수가 그 일부일 뿐이라는 것을 알 수 있습니다.
우리가 모든 *를 F (6)에서 F (2) 행으로 F (1) 행으로 정신적으로 이동 시키면, F (1)과 F (0) 행의 길이가 같다는 것을 알 수 있습니다. 즉, n = 6이 2×32 = 64 = 2 ^ 6 일 때 F ()가 호출되는 총 횟수입니다.
이제 복잡성 측면에서 :
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
답변
MIT 에서이 특정 문제에 대해 아주 좋은 토론이 있습니다. 5 페이지에서 추가에 하나의 계산 단위가 필요하다고 가정하면 Fib (N)을 계산하는 데 필요한 시간은 Fib (N)의 결과와 매우 밀접한 관련이 있습니다.
결과적으로 피보나치 계열의 매우 가까운 근사치로 바로 건너 뛸 수 있습니다.
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
따라서 순진 알고리즘의 최악의 성능은
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
추신 : 자세한 정보를 원하시면 Wikipedia에서 N 번째 피보나치 수 의 닫힌 형태 표현에 대한 토론이 있습니다 .
답변
당신은 그것을 확장하고 visulization 할 수 있습니다
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)
타이트 바운드는 원하는 경우 닫힌 형태를 .
답변
증명 답변은 좋지만, 항상 자신을 확신시키기 위해 손으로 몇 번 반복해야합니다. 그래서 화이트 보드에 작은 호출 트리를 그리고 노드 계산을 시작했습니다. 카운트를 총 노드, 리프 노드 및 내부 노드로 나눕니다. 내가 가진 것은 다음과 같습니다.
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))입니다.
