递归的时间复杂度

Question

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

g(2x)=(2g(x)) / (1+g^2(x))...-1<=x<=1...对于|x|

老实说，我不知道如何递归地编写代码。在运行完代码之后，我们要用大的哦符号写出时间复杂度，但是我仍然停留在第一步。任何帮助解释的人都将不胜感激，因为我在期末考试中没有这方面的问题。

Answer 1

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

而且，这样的程序的复杂性以某种方式与圈复杂度(也就是说，表达算法所需的最小数量的嵌套循环或递归调用)有关。在您的例子中，复杂度是O(n) (如果只需要一个循环)或O(n^2) (如果需要两个嵌套循环)。

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