単純な再帰的メソッドの大きなOを決定するのが難しいです。これらのメソッドのためにbig-Oをどのように計算できますか？再帰的メソッドの大きな部分
ケース1）メソッドfのビッグOを見つける：
int f(int x){
if(x<1) return 1;
return f(x-1)+g(x);
}
int g(int x){
if(x<2) return 1;
return f(x-1)+g(x/2);
}
ケース2）
int test(int n){
if(x<=2) return 1;
return test(n-2) * test(n-2);
}
ケース3）
int T(int n){
if(n<=1) return 1;
return T(n/2)+T(n/2);
}
ケース1
さておき（g(1) = g(0) = 1など）をベースケースの設定、あなたはfの面でgを書き換えることができます。私たちが持つg(n/2)を交換する場合
g(n) = f(n-1) + g(n/2)
：
f(n) = f(n-1) + g(n) <=> g(n) = f(n)-f(n-1)
を私たちはgは次のように定義されていることを知っています上記書き換えられたフォームは、我々が得る：
g(n) = f(n-1) + f(n/2) + f(n/2-1)
我々はfウィットを書き換えることができることを意味していますハウトgへの参照は、上記の式でfの元の定義にg(n)を交換することにより：これは同等であることをダブルチェックするために
f(n) = f(n-1) + f(n-1) + f(n/2) + f(n/2-1)
、あなたは最初の引数として整数nを受け入れ、このプログラムを実行することができます、およびf(n)の書き換え形続くオリジナルf(n)の結果を出力し（コードでf2と呼ばれる）：
#include <stdio.h>
int g(int x);
int f(int x) {
if (x < 1)
return 1;
return f(x-1)+g(x);
}
int g(int x) {
if (x < 2)
return 1;
return f(x-1)+g(x/2);
}
int f2(int x) {
if (x < 1)
return 1;
return f2(x-1)+f2(x-1)+f2(x/2)-f2(x/2-1);
}
int main(int argc, char *argv[]) {
int n;
sscanf(argv[1], "%d", &n);
printf("%d\n", f(n));
printf("%d\n", f2(n));
return 0;
}
いくつかの例：
今$ ./a.out 10
1952
1952
$ ./a.out 11
3932
3932
$ ./a.out 12
7923
7923
$ ./a.out 13
15905
15905
$ ./a.out 14
31928
31928
$ ./a.out 15
63974
63974
、あなたは4つのサブツリー（f(n-1)ごとに1つ、f(n-1)、f(n/2)とf(n/2-1)）に、各ノードの枝を再帰ツリーをオフに想像している場合。各サブツリーのサイズは同じではありません。たとえば、サブツリーに降りて常に2つの最も右のブランチのいずれかに従うと、深さがlog(N)のバイナリツリーがあります。しかし、深さがnである別のブランチ（常にf(n-1)パスに従っている場合）があり、それはn-1に2回分岐します。このため、それは明らかに指数関数的であると言えるでしょう。
それは正確な数を取得するには少し難しいですが、明白な上限はO(4^N)ある - これは、いくつかの枝が唯一log(N)深いですので、実際にそれがO(4^N)より少しはましだという事実を無視しても。
ケース2
再び再帰ツリーについて考えてみてください。それぞれのポイントで2回分岐します（test(n-2)とtest(n-2)）。呼び出しごとにnを2減らすので、ツリーはO(n/2)と深くなるので、ツリーをトラバースする時間は、O(2^(n/2))になる必要があります（指数関数的な増加）。特に興味深いのではない。
（メモ：ここでメモを使用する場合、これは線形です！）。
ケース2とケース3
同様のロジックが、今回は木が（それはあなたが基本ケースに到達するために2によってNを分割する必要がありますどのように多くの回だから）深log(N)を持っているので、我々が得ます2^log(N) = N。だから線形です。