再帰による時間の複雑さ

Question

私は自分のデータ構造のクラスに宿題の問題があるので、助けが必要です。次の再帰関数をコード化する必要があります。

g（2g）=（2g（x））/（1 + g^2（x））... -1 < = x < = 1 ... | E（イプシロン）.... E = 10^-6 ..... g（x）= x + x3/6 .... dx = 10^-1のコード。

正直なところ、これを再帰的にコーディングする方法はわかりません。コードを実行した後、時間の複雑さを大きな表記で書き留めますが、私はまだステップ1に固執しています。この行に沿った問題は最終的には解決されません。

Answer 1

whileループをイプシロンの値以上に使用することができます（または再帰呼び出しによって実装することができます）。おおよその近似値（10^-6）を近似する必要がある場合は、それを止めます。

そして、そのようなプログラムの複雑さは、何らかの形で循環的複雑さに関係しています（つまり、アルゴリズムを表現するのに必要なネストされたループまたは再帰呼び出しの最小数）。あなたのケースでは、複雑さはO（n）（ループが1つだけ必要な場合）またはO（n^2）（2つのネストループが必要な場合）にあります。

dxは、あなたの近似関数のステップです。