c++ - 递归的时间复杂度

Question

好吧，我需要一些帮助来解决我在数据结构课上遇到​​的作业问题。我们要为以下代码编写一个递归函数。

g(2x)=(2g(x))/(1+g^2(x))... -1<=x<=1... 对于|x| < E (epsilon).... E=10^-6.....g(x)=x+x3/6....dx=10^-1 的代码。

老实说，我不知道如何递归地编写代码。运行代码后，我们将用大 oh 符号写出时间复杂度，但我仍然停留在第一步。任何解释方面的帮助将不胜感激，因为我在这条线上没有问题将在最后

Answer 1

您可以对 epsilon 的值使用 while 循环(或通过递归调用实现)。一旦您的近似值足够接近 (10^-6) 您需要近似的值，您就可以停止。

并且，此类程序的复杂性以某种方式与圈复杂度相关(也就是说，表达算法所需的嵌套循环或递归调用的最少数量)。在您的情况下，复杂度为 O(n)(如果您只需要一个循环)或 O(n^2)(如果您需要两个嵌套循环)。

请注意，dx 是您的近似函数的步长。