performance - 求解递归公式的高效算法

Question

我得到一个公式 f(n)，其中 f(n) 的定义是，对于所有非负整数，如下:

f(0) = 1

f(1) = 1

f(2) = 2

f(2n) = f(n) + f(n + 1) + n (for n > 1)

f(2n + 1) = f(n - 1) + f(n) + 1 (for n >= 1)

我的目标是，对于任何给定的数字 s，找到最大的 n，其中 f(n) = s。如果没有这样的 n 则返回 None。 s 最大为 10^25。

我有一个同时使用递归和动态规划的强力解决方案，但两者都不够有效。哪些概念可以帮助我找到解决此问题的有效方法？

Answer 1

我想添加一点复杂性分析并估计 f(n) 的大小。

如果你看一下 f(n) 的一次递归调用，你会注意到，输入 n 在调用 f(n) 两次之前基本上除以 2，其中总是有一次调用一个偶数和一个奇数输入。
所以调用树基本上是一棵二叉树，其中特定深度 k 上的一半节点总是提供大约 n/2^k+1 的加数。树的深度是 log2(n)。

所以 f(n) 的总和约为 Θ(n/2 ⋅ log2(n))。

请注意:这适用于偶数和奇数输入，但对于偶数输入，该值大约是一个额外的加数 n/2 更大。 (我使用 Θ 表示法不必过多考虑某些常量)。

现在复杂的是:

朴素暴力

要计算 f(n)，您必须调用 f(n) Θ(2^log₂(n)) = Θ(n) 次。
所以如果你想计算 f(n) 的值直到你到达 s(或者注意到 f(n)=s 时没有 n)你必须计算 f(n) s⋅log₂(s) 次，这总共是 Θ(s²⋅log(s))。

动态编程

如果您存储 f(n) 的每个结果，计算 f(n) 的时间将减少到 Θ(1)(但它需要更多的内存)。因此，总时间复杂度将降低为 Θ(s⋅log(s))。

注意:由于我们知道对于所有 n，f(n) ≤ f(n+2)，因此您不必对 f(n) 的值进行排序并进行二分查找。

使用二分查找

算法(输入为s):

1. 设置l = 1 和r = s
2. 设n = (l+r)/2，四舍五入为下一个偶数
3. 计算 val = f(n)。
4. 如果 val == s 则返回 n。
5. 如果 val < s 则设置 l = n
   否则设置 r = n。
6. 转到2

如果您找到了解决方案，那很好。如果不是:再试一次，但在第 2 步中四舍五入为奇数。如果这也没有返回解决方案，则根本不存在解决方案。

这将用 Θ(log(s)) 进行二分查找，每次用 Θ(s) 计算 f(n)，所以总共得到 Θ(s⋅log(s))。

如您所见，这与动态规划解决方案具有相同的复杂性，但您无需保存任何内容。

注意:r = s 并不适用于所有 s 作为初始上限。然而，如果 s 足够大，它成立。为了保存，您可以更改算法:
首先检查 f(s) < s。如果不是，您可以设置 l = s 和 r = 2s(如果必须为奇数，则设置为 2s+1)。