1

我一直在玩 wolfram 语言并注意到一些事情：以不同方式编写的相同函数在时间方面的工作方式非常不同。

考虑这两个函数：

NthFibonacci[num_] := 
 If [num == 0 || num == 1, Return[ 1], 
   Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
 ]

Fibn[num_] := {
 a = 1; 
 b =  1; 
 For[i = 0, i < num  - 1, i++,
  c = a + b;
  a = b;
  b = c;
  ];
 Return [b];
 }

NthFibonacci[30]评估大约需要 5 秒。
Fibn[900 000]也需要大约 5 秒来评估。
内置也是如此Fibonacci[50 000 000]

我根本不明白为什么三者之间的速度有如此大的差异。理论上，递归应该或多或少等同于 for 循环。这是什么原因造成的？

4

3 回答 3

3

这是因为您提供的递归版本进行了大量的重复计算。构建一个函数调用树，看看我的意思。即使对于小到 4 的参数，也要查看生成了多少函数调用才能到达逻辑的每个链的基本情况。

                 f(1)
                /
            f(2)
           /    \
       f(3)      f(0)
      /    \
     /      f(1)
    /
f(4)
    \
     \      f(1)
      \    /
       f(2)
           \
            f(0)

随着您的递归，函数调用的数量随着参数呈指数增长num。

相比之下，您的循环版本在num. 它不需要很大的值nbeforen比2 n少很多工作。

于 2016-06-28T14:22:20.280 回答
1

实现递归的方法有很多；斐波那契函数就是一个很好的例子。正如pjs已经指出的那样，经典的双递归定义呈指数增长。基础是

φ = (sqrt(5)+1) / 2 = 1.618+

您的NthFibonacci实现以这种方式工作。它是 φ^n 阶，这意味着对于较大的n，调用 f(n+1) 所需的 φ 倍时间是 f(n)。

更温和的方法在执行流中只计算每个函数值一次。它不是指数时间，而是线性时间，这意味着调用 f(2n) 需要的时间是 f(n) 的 2 倍。

还有其他方法。例如，动态规划 (DP) 会保留先前结果的缓存。在pjs f(4) 的情况下，DP 实现将只计算 f(2) 一次；第二次调用将看到第一次的结果在缓存中，并返回结果而不是进一步调用 f(0) 和 f(1)。这倾向于线性时间。

还有一些实现可以创建检查点，例如缓存 f(k) 和 f(k)+1 以使 k 可被 1000 整除。这些可以节省时间，因为它们的起点不会远低于所需值，因此它们的上限为998 次迭代以找到所需的值。

最终，最快的实现使用直接计算（至少对于较大的数字）并在恒定时间内工作。

φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)
于 2016-06-28T16:56:21.710 回答
0

@pjs 指出的问题可以通过让递归函数记住先前的值来解决。（也消除了If帮助）

Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] := 
 NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming

{0.00201479, 3.59 10^62}

清理你的循环版本（你几乎不应该Return在mathematica中使用）：

Fibn[num_] := Module[{a = 1, b = 1,c},
  Do[c = a + b; a = b; b = c, {num - 1}]; b]

Fibn[300] // AbsoluteTiming

{0.000522175 ,3.59 10^62}

您会看到递归形式较慢，但并非如此。（注意递归形式也达到了 1000 左右的深度限制）

于 2016-06-28T18:05:46.443 回答