4

我正在研究一个算法问题，而我在加速它时遇到了障碍。

我有一个函数f(i,j)，其中i和j是整数，因此1 <= i <= j <= n对于某些上限n。这个函数已经写好了。

此外，这个函数满足等式f(i, j) + f(j, k) = f(i, k)。

我需要计算f(x, y)许多不同的对x, y。假设n足够大，存储f(x,y)每一对可能的对x,y将占用太多空间。

这类问题有已知的算法吗？我现在使用的那个记忆f并试图x,y通过使用上面提到的相等性来减少到先前计算的一对数字，但我的猜测是我没有以一种聪明的方式减少，这会浪费我的时间。

编辑：假设f(i, j)时间与以j-i天真的方式计算时成正比。

4

3 回答 3

6

您可以使用大小为 2 的间隔的隐式树：

  • f(i,i+1)为每个人存储i
  • f(i,i+2)为每个偶数存储i
  • 存储f(i,i+4)每i被四整除
  • ...

将有O(log n)表格（floor(log_2(n))准确地说），总大小为O(n)（~ 2*n）。

要检索f(i,j)where i<=j：

  • 找到不同的最高i位j。
  • 设为n设置此位的值，并清除所有低位。这保证了以下步骤将始终成功：
  • f(i, n)通过从右侧重复切掉尽可能大的块来查找
  • f(n, j)通过从左侧重复切掉尽可能大的块来查找

检索最多访问每个表两次，因此在O(log n).

于 2013-04-08T08:43:34.793 回答
2

函数满足规则

f(i, j) + f(j, k) = f(i, k)

正如你所说 。

所以将函数修改为 f(i,j) =g(j)-g(i) ，其中 g(i)= f(1,x)

这样

f(i,k)=g(k)-g(i)
      =g(k)-g(j)+g(j)-g(i)
      =f(j,k) + f(i,j)

所以我认为如果你尝试存储 f(i,j) 的所有组合，它会花费你大约 o(n^2) 空间，所以你最好为 i 的所有值存储 g(i) 值的值o(n) 空间

因此，当您需要查找 f(i,j) 时，您实际上可以将其查找为 g(j)-g(i) 。

作为

  f(i,j)= g(j)-g(i) // as we already calculated and stored the g(i) .
于 2013-04-08T08:53:55.470 回答
0

这是一个需要O(n)空间、O(n^2)设置时间和O(1)每次评估时间的解决方案。

我们有那个f(i, j) = -f(j, i)。i <= j

给定的是f(i, k) = f(i, j) + f(j, k)。因此，f(i, k) = f(i, j) + f(j, k) = -f(j, i) + f(j, k)。在设置阶段，j = 1任意修复。然后，计算f(1, i)每个i并存储结果。这需要O(n)空间和O(n^2)时间：n运行时间为1, 2, 3, ..., n.

对于查询，我们需要对和f(i, k)进行两次恒定时间查找。f(i, 1)f(k, 1)

于 2013-04-08T09:00:42.053 回答