我正在研究一个算法问题，但在加快速度方面遇到了瓶颈。
我有一个函数 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 成正比当以朴素的方式计算时。
最佳答案
您可以使用二次方大小间隔的隐式树:
- 商店
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)其中 i<=j :
- 找到
i的最高位,j不同。 - 让
n是设置此位且清除所有低位的值。这保证了以下步骤将始终成功: - 找到
f(i, n)反复从右侧切掉尽可能大的 block - 找到
f(n, j)通过从左侧重复切掉尽可能大的 block
retreival 最多访问每个表两次，因此在 O(log n) 中运行.
关于algorithm - 区间动态规划，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15874244/