如何计算递归函数的值？

Question

我有递归函数：T(n) = 2T(n/2) + n。我想通过将不同的参数传递给函数并获取函数的值来找到函数的复杂性。然后我会猜测函数的公式（例如n，n * log（n））。

我写了下面的代码：

public static void main(String[] args) {
    System.out.println(findValueOfTheFunction(2));
    System.out.println(findValueOfTheFunction(4));
    System.out.println(findValueOfTheFunction(8));
}

static double findValueOfTheFunction(double n) {
    if(n > eps) {
        return 2*findValueOfTheFunction(n/2) + n;
    }
    else return 0;
}}

我从代码中得到了三分。 p1(2, 10) 和 p2(4, 24) 和 p3(8, 56)。

据了解，递归函数的复杂度为O(n) = n*log(n)。但是我的观点不符合公式。

我在这里做了一些研究，但似乎没有人有类似的问题。

Answer 1

你的第一个问题在这里：

 else return 0;

在某个时候；你的递归结束；并达到如果。

然后您开始乘以最后一次调用的结果...然后猜猜 x * y * z * ... * 0 可能会计算出什么？！

所以您的方法所做的只是 returning 一些 m * n 值（其中 n 是您的输入；m 取决于您递归调用您自己的方法的频率。因为您的代码转换为：

  if (n>eps) {
    return n + findValueOfTheFunction(n/2)

长话短说：您的计算丢失了结果的 "interesting" 部分。所以 - 而不是 returning 0 ... return 1!

Answer 2

你必须为此编写代码吗？您可以通过给 n 赋值然后替换来做一些数学运算：

t(1) = 2t(1/2) + 1
t(2) = 2t(1) + 1 = 2(2t(1/2)+1) = 2*2t(1/2)
t(4) = 2t(2) + 1 = 2*2*2*t(1/2)
t(8) = 2t(4) + 1 = 2*2*2*2*t(1/2)

剩下的2*1不是那么重要，你可以继续留在t(1/2)部分。我猜已经有事情发生了。

如何计算递归函数的值？

How to calculate value of the recursive function?

java

recursion

asymptotic-complexity