指数関数時間アルゴリズムの簡単なコード例はありますか？

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）。フィボナッチ級数の対数グラフを見ると、指数関数的に増加していることがわかります。

解決策はもちろん動的プログラミングです。これまでに計算したフィボナッチ級数の要素を格納し、ルックアップテーブルとしてストレージに使用します。