현재 컴퓨터에서 n 번째 피보나치 수를 계산하는 데 얼마나 많은 시간이 필요한지 아는 방법은 무엇입니까? 예를 들어, 현재 시스템에서 30 번째 요소는 67ms에서 계산되고 40 번째 요소는 554ms에서 계산됩니다. 99 번째 요소의 시간을 계산하는 방법은 무엇입니까?n 번째 피보나치 수의 재귀 계산 시간을 계산하는 방법은 무엇입니까?
int fib(int n)
{
if(n <= 2)
return 1
else
return fib(n-1) + fib(n-2)
}
UPDATE
피보나치 N 번째 대 MS http://pastebin.com/PGnd54Hq
matlab에 (시간 현재 PC는 n 번째 피보나치 요소, MS 시간 계산했다) : 코드 http://pastebin.com/L9CH53Pf
을
N 번째 요소의 시간을 찾는 방법은 무엇입니까?
나는 값의 범위에 대한 시간을 측정하고 테이블을 만들 것입니다 : 다음
n | time
과는 exponential function에 맞게 matlab를 사용합니다. 당신이 큰 O 표기법은 점근 적이며 요소의 큰 번호를 보유하고 있다는 사실을
당신은 그것을 위해 C 코드를 작성하려고합니다. 피보나치 루틴의 인라인 함수를 사용하고 ctime을 사용하여 시간을 얻고 두 개의 arraies에 값을 저장하십시오. 그 후에는 matlab 또는`python을 사용하여 결과를 분석합니다.
당신의 결과를 게시하시기 바랍니다 ...
이 함수에 재귀 호출의 수는 피보나치 순서를 따른다는 것을 증명하기 쉽다. 마찬가지로 F0=0 및 F1=1이 기본 사례 인 경우 F2은 함수를 2 번 호출해야하고 F3은 3을 필요로합니다.
이는 @ 0x90이 제안한대로 지수 함수를 사용하여 시간을 맞추는 것을 정당화합니다.
분명히 피보나치 시퀀스를 계산하기위한 순진한 알고리즘을 구현하고 있습니다. 이 알고리즘의 지수는 다음과 같습니다. Computational complexity of Fibonacci Sequence (~ θ(1.6n)). 컴퓨터에서 프로그램을 실행하는 시간은 대략 k*1.6n입니다.n에 대한 함수 (프로그램 실행 시간)를 알면 상수 k을 계산할 수 있어야하고 n에 대한 대략적인 시간을 계산할 수 있어야합니다.
이 수식에 실시간 알고리즘이 필요하지 않은 이유를 이해할 수 없습니다. 문제의 예에서 40 번째 요소를 계산하는 데 걸리는 시간은 554ms와 30-67ms입니다. 이 공식 k = (67/(1.6^30)) 및 T [40] = ((67/(1.6^30)) * 1.6^(40)을 사용하면 올바르지 않습니다. http://www.wolframalpha.com/input/?i=%28%2867%2F%281.6%5E30%29%29*1.6%5E%2840%29%29 –
나열된 코드에서 각 통화는 2 회 전화를 겁니다. 따라서이 질문에 대한 간단한 대답은 각 n에 대해 호출 수가 두 배가되므로 호출 수가 2^(n-1)입니다. 예를 들어, fib (10)을 계산할 경우 호출 수는 2^9 = 512가됩니다. 따라서 1을 만들기 위해 1 초가 걸리면 fib (10)를 호출하는 데 512 초가 걸립니다.).
성능은 함수 호출 수와 각 호출 내부의 계산 수에 의해 결정될뿐만 아니라 재귀 알고리즘으로 인해 스택에서 더 많은 시간을 밀기 위해 지불하는 시간에 따라 결정됩니다. 스택 푸싱이 어떻게 실행되는지는 모르지만 특정 임계 값 이후에 더 빠르게 증가하기 시작할 수 있습니다. 따라서,이 임계 값이 어디에서 발생하는지 알아 내야합니다 (기하 급수적 으로든 뭐든간에) 아래와 위 모두에 맞아야합니다 (재귀 적 스택을 빌드하기 시작할 때 비슷한 성능 저하가있을 수 있습니다).
분명히 - 문제는 아니지만 피보나치 숫자는 수학적으로 우아하고 가장 간단한 코드가 필요하지만 재귀 적 방식으로 계산해서는 안됩니다.
[ADDED/EDITED] 시간 측정 그래프를 추가 한 것으로 나타났습니다. 보다 나은 통찰력을 얻으려면 LOGARITHMIC 스케일을 수직 (시간)으로 사용하는 것이 좋습니다. 이것은 전체 그래프가 "순전히"지수 함수인지 - 대수 플롯의 직선인지 - 아니면 (다른) 지수의 순서인지 아니면 다른 것이지 여부를보다 명확하게 보여줍니다. 어쩌면 지수 부분이 "어딘가"로 시작하거나 다른 지수로 변경 될 수 있습니다.
"현재 컴퓨터"는 무엇을 의미합니까? 문제는 불분명하다. 또한 모든 종류의 추정은 알고리즘의 종류에 따라 달라집니다. 그것은 꼬리 재귀인가? 매 호출마다 스택 프레임을 밀고 있습니까? 이 질문으로 무엇을 얻고 있습니까? –
내 컴퓨터 - 현재 PC에서 재귀 알고리즘이 실행 중입니다. 아마도 또 다른 가능한 해결책은 얼마나 많은 단계가 필요한지 (전체적으로) 파악하고 이것을 한 단계의 시간으로 곱하는 것입니다. 그러나 한 단계에 필요한 시간을 어떻게 계산할 수 있습니까? –