如何计算递归函数的值？

我有递归函数：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）。但是我的观点不符合公式。

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

来源

2016-11-25 Artmal

你说的'O（N）= N *的log（n）'是什么意思？大哦表示法不是公式，它是上限 –

算法的复杂性与输出无关。这是关于获得输出需要多少时间。 – 4castle

这个任务听起来像这样：“递归函数T（n）= 2T（n/2）+ n描述了一些算法，通过找到不同n的函数值，然后猜测公式，找出算法的复杂性。 – Artmal

你的第一个问题是在这里：

else return 0;

在某一点;你的递归结束;并达到如果。

，然后你开始乘以最后一次调用的结果......你猜怎么X * Y * Z * ...... * 0可能计算到？！

因此，所有你的方法做的是将一些m * n个值（其中n是你的输入;以及M取决于你递归如何常称自己的方法，你的代码转换为：

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

。长话短说：！？你的计算失去其结果的“有趣”的一部分，所以 - 而不是返回0 ...返回1

来源

2016-11-25 19:58:16 GhostCat

在这种情况下，我应该停止递归？ – Artmal

看到我更新的答案：关键是你不应该返回一个值“丢弃”递归**乘法**！记录：我不确认你对n * log（n）的假设是真/假。我所说的是：你的**代码**不符合所需函数T（n）= 2T（n/2）+ n。 – GhostCat

你有没有为此编写代码，您可以通过在给予值做一些数学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）部分。我猜测已经有些事了。

来源

2016-11-25 20:23:00 selimssevgi

如何计算递归函数的值？

回答

相关问题