지수 시간 알고리즘의 쉬운 코드 예제가 있습니까?

Question

나는 지수 적 가능성을 발생시키고 그것을 반복하는 것에 대해 이야기하는 알고리즘을 안다. 하지만 누구나 코드가 모든 사례를 통과하고 답을 찾는 의사 코드를 내게 줄 수 있습니까?

Answer 1

예, 있습니다. 동적 프로그래밍없이 피보나치 시리즈를 계산하는 데 사용되는 간단한 알고리즘이 가장 좋은 예입니다.

int f(n) 
{ 
if(f == 0 || f == 1) 
    return 1; 
return f(n-1)+f(n-2); 
} 

이 코드는 기각적인 시간이 걸립니다. f(n)을 계산하는 시간은 피보나치 수 n+1에 비례합니다. 이것을 link에서 피보나치 시리즈의 성장에 대해 알 수 있습니다 (제공 : David Leese의 blog). 피보나치 시리즈의 대수 그래프를 보면 기하 급수적 인 증가를 볼 수 있습니다.

물론 솔루션은 동적 프로그래밍입니다. 지금까지 계산 한 피보나치 시리즈 요소를 저장하고 룩업 테이블로 저장소를 사용하십시오.