フィボナッチ数列
時間と複雑さの分析に問題があります。私はフィボナッチ数列を再帰的に実行しました。O（n 2）だと思います。時間分析を見つけることができますか？可能であれば、詳しく説明していただけますか？
#include<iostream>
using namespace std;
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
int main()
{
int n;
cout<<"Enter the number:"<<endl;
cin>>n;
fibonacci(n,0,1);
return 0;
}
回答
答えのどれかがまだ本当に複雑さに対処しているかどうかはわかりません。時間の複雑さを変えることなく、アルゴリズムをより単純なものに変換することで、これを実現します。これは、時間の複雑さを証明するだけでなく、読みやすく、推論しやすいバージョンのアルゴリズムを提供します。
ソリューションから始めましょう
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
そのelse if部分は実際には必要ないので、それを削除して、余分なreturnコマンドも削除しましょう。[このステップが見た目ほど無害ではない理由については、コメントを参照してください。]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
を逆にしifます。また、それらreturnの1つを元に戻し、elseパーツから印刷を削除します。
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
末尾再帰の最適化を適用します。つまり、再帰呼び出しとそれに続く戻り値を、パラメーターの再割り当てとサブルーチンの先頭へのジャンプに置き換えます。この手順により、スペースの複雑さ*は変更されますが、時間の複雑さは変更されません。
void fibonacci(int n,int n1,int n2)
{
start:
if(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ;
goto start ; }
out<<endl<<n1;
}
の代わりにループを使用しますgoto。
void fibonacci(int n,int n1,int n2)
{
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
パラメータがパラメータである必要はありません。私はおそらくサブルーチンを文書化するので、それが何をするのかは明らかです。そして、whileループを不変条件で文書化するので、それがどのように機能するかがより明確になります。
void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
// preceded by an end of line.
{
int n1 = 0 ;
int n2 = 1 ;
// Let n0 be the original value if n.
// invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1)
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
（もちろん、それが呼ばれる場所も変更します。）
この時点で、アルゴリズムがO（n）であることは明らかです（私は思います）。どの変換も時間計算量を変更しないため、元の変換の時間計算量もO（n）です。
（*）つまり、コンパイラが末尾再帰の最適化を行わない限り、スペースの複雑さはO（n）からO（1）に変更されます。もしそうなら、スペースの複雑さは最初からO（1）でした。
約 using namespace std
このステートメントは悪い習慣と見なされるため、避けるようにしてください。できる限りそれを避けるのが最善です。これがその理由の簡単な例です。
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
もう1つの問題は、プロジェクトのヘッダーファイルのいずれかにこれがある場合、ヘッダーをインクルードしたすべてのファイルでこれを使用することを余儀なくされることです。
名前空間stdの使用が悪い習慣と見なされるのはなぜですか
テンプレートメタプログラミング
これにより、計算が実行時からコンパイル時に移動します。プログラムのコンパイルには少し時間がかかりますが、複雑さはになりますO(1)。C ++のテンプレートを使用して、コンパイラーに値の計算を強制します。
これは、この問題に取り組むためのもう1つのオプションであり、計算がコンパイル時に移動するため、最速の方法です。
ただし、欠点は、コンパイル時に不明な値を使用できないことです。たとえば5、ユーザーが入力するものの値を見つけることはできますが、それを見つけることはできません。たとえば、乱数を生成することもできます。
#include<iostream>
template <unsigned N>
struct Fibonacci
{
enum : uint64_t
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
int main()
{
std::cout << Fibonacci<20>::value;
}
この方法は最速ですが、数値が一定の場合にのみ機能します。
C ++でのテンプレートメタプログラミング
再帰を反復に置き換えます
再帰によってコードは少しクリーンになりますが、ほとんどの場合、再帰の実行速度は遅くなります。これは、呼び出しごとに新しいスタックフレームを割り当てる必要があるためです。スタック
内のスペースは有限であるため、再帰呼び出しの数には制限があります。 C ++があなたに与える前にあなたは作ることができます0xC00000FD。これはスタックオーバーフロー
です。コードを数行追加することで、再帰をこのシナリオに置き換えて、この問題なしにはるかに高速にすることができます。
これは、再帰を使用すべきではないという意味ではありません。一部のアルゴリズムでは再帰が必要ですが、再帰に置き換えることができれば、それだけの価値があります。
これが反復です。
uint64_t fibonacci(int n)
{
uint64_t n1 = 0,n2 = 1,n3 = 1;
if (n == 1 || n == 0) return 0;
else if(n == 2) return 1;
for (int i = 2;i < n;++i)
{
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
'\n' 以上 std::endl
'\n'そして、std::endlの両方が、あなたのタスクを達成しますが、std::endl呼び出し、std::flushそれは簡単に印刷するよりも、遅くなります、なぜこれが、毎回、ストリームをフラッシュ'\n'
std :: endlと '\ n'の比較
fibを書く最も明白な方法：
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
fib（）を呼び出すたびに、2つの後続の呼び出しがあり、両方とも2つの呼び出しがあり、すべてが2つの呼び出しがあるため、爆発していることがわかります。
Level Calls Calls This Level Total Calls
Level n 1 1 1
Level n-1 1 1 2 3
Level n-2 1 1 1 1 4 7
Level n-3 1 1 1 1 1 1 1 1 8 15
したがって、Fibの複雑さはFibです!!!!!
より正確にはO(2Fib(n)-1)
、完全性は定数を削除することですO(Fib(n))
これを検証するためのコードを書いてみましょう。
int fibComplexity(int n)
{
// has the same properties of fib.
// but returns the number of calls rather than the value.
if (n < 2)
{
return 1; // You called this function once.
}
return 1 // the call to this function.
+ fibComplexity(n-1) // Count of calls in this tree
+ fibComplexity(n-2) // Count of calls in this tree.
}
これを実行した場合：
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
生成:(追加されたフォーマット）
n F O
2 2 3
3 3 5
4 5 9
5 8 15
6 13 25
7 21 41
8 34 67
9 55 109
10 89 177
11 144 287
12 233 465
13 377 753
14 610 1219 O = 2f-1
しかし、受講するすべてのコーディングコースでは、線形ベースのソリューションを作成するように求められます。
上に示したのは再帰的です（ただし線形解です）。ほとんどの人はループベースの線形ソリューションを選択します（ただし、違いはありません）。複雑さはまったく同じです。
あなたがしたことは、あなたが行くにつれて物事を追加する関数を再帰的に呼び出すことです。各呼び出しは、追加の呼び出しを1回だけ行いますが、深さはnだけです。その後、戻ります。
したがって、の複雑さがありO(n)ます。
しかし、これをさらに一歩進めることができます。fibアルゴリズムは、として簡単に実装できますO(1)。
これは、fibが整数のサイズをすぐに超えてしまうためです（長い場合でも）。変数に格納できるすべての有効な値を簡単に事前に計算して、それらを配列に入れることができます。次に、結果を調べて値を返すだけです。
int fib(int n) {
static const int fibValue[] = { ... };
if (n < 0 || n > std::size(fibValue)) {
// This is 47 for 32 bit ints
// 93 for 64 bit ints
throw "Result out of range"
}
return fibValue[n];
}
明確にするために：あなたは\$O(n)\$時間と \$O(n)\$メモリ内。整数演算（実際に計算するとき）を時間内に簡単に改善できるとは思いませんが、メモリは\$O(1)\$。
Peter Cordesが指摘しているように、フィボナッチ数列には「閉じた形」があります。つまり、一定時間の無限精度の浮動小数点システムを使用している場合は、\を達成できます。$O(1)\$。コンピューターの浮動小数点は近似を達成できますが、整数演算でより正確な結果が得られると思います。
Peter Cordesも指摘しているように、\を実行できる「Lucasシーケンスメソッド」があります。$O(\log{n})\$ 整数の乗算とかなり複雑なものが与えられます。
関数を繰り返し使用してフィボナッチ数列を出力すると、時間の結果は\になります。$O(n^2)\$、そしてそれは\で行うことができます$O(n)\$。