有效确定矩阵中 元素的算法

这是一个关于课程作业的问题，所以宁愿你没有完全回答这个问题，而是提出改进我当前算法的运行时复杂性的技巧。

我收到了以下信息：

函数g（n）由g（n）= f（n，n）给出，其中f可以递归地定义

我用以下代码递归地实现了这个算法：

public static double f(int i, int j) { if (i == 0 && j == 0) { return 0; } if (i ==0 || j == 0) { return 1; } return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3; } 

这个算法给出了我正在寻找的结果，但效率极低，我现在的任务是改善运行时的复杂性。

我写了一个算法来创建一个n * n矩阵，然后计算每个元素直到[n] [n]元素，然后它返回[n] [n]元素，例如f（1,1）返回0.6重复出现。 [n] [n]元素重复为0.6，因为它是（1 + 0 + 1）/ 3的结果。

我还创建了一个结果从f（0,0）到f（7,7）的电子表格，如下所示：

现在虽然这比我的递归算法快得多，但是它创建一个* n矩阵的开销很大。

任何有关如何改进此算法的建议将不胜感激！

我现在可以看到，有可能使算法O（n）复杂，但是可以在不创建[n] [n] 2D数组的情况下计算出结果吗？

我已经在Java中创建了一个在O（n）时间和O（n）空间中运行的解决方案，并且在我递交课程以阻止任何剽窃之后将发布解决方案。

Answer 1

在潜入和编写代码之前，这是另一个最好检查它的问题。

我要说你应该做的第一件事就是看一下数字的网格，而不是将它们表示为小数，而是分数。

首先应该明显的是总数 你只是衡量距起源的距离， 。

如果以这种方式查看网格，您可以获得所有分母：

请注意，第一行和第一行不是全部1秒 – 它们已被选择为遵循模式，并且通用公式适用于所有其他正方形。

分子有点棘手，但仍然可行。 与大多数这样的问题一样，答案与组合，阶乘，然后是一些更复杂的事情有关。 这里的典型条目包括加泰罗尼亚数字 ， 斯特林数字 ， Pascal三角形 ，您几乎总会看到使用的超几何函数 。

除非你做了很多数学，否则你不太可能熟悉所有这些，而且还有很多文献。 所以我有一个更简单的方法来找出你需要的关系，这几乎总是有效的。 它是这样的：

1. 写一个天真的，低效的算法来获得你想要的序列。
2. 将相当大量的数字复制到谷歌中。

3. 希望突然出现在线整数序列百科全书的结果。

   3.B. 如果没有，那么请查看序列中的某些差异，或与您的数据相关的其他序列。

4. 使用您找到的信息来实现所述序列。

所以，按照这个逻辑，这里是分子：

现在，不幸的是，谷歌搜索没有产生任何东西。 但是，有一些事情你可以注意到它们，主要是第一行/列只是3的幂，第二行/列比3的幂少一个。 这种边界与Pascal的三角形和许多相关序列完全相同。

这是分子和分母之间的差异矩阵：

我们已经确定f（0,0）元素应该遵循相同的模式。 这些数字看起来已经简单得多了。 还要注意 – 相当有趣的是，这些数字遵循与初始数字相同的规则 – 除了第一个数字是一个（并且它们被列和行偏移）。 T(i,j) = T(i-1,j) + T(i,j-1) + 3*T(i-1,j-1) ：

  1 1 1 1 5 1 1 9 9 1 1 13 33 13 1 1 17 73 73 17 1 1 21 129 245 192 21 1 1 25 201 593 593 201 25 1 

这看起来更像是你在组合学中看到很多的序列。

如果您使用此矩阵中的Google数字，则会受到影响。

然后，如果你切断了原始数据的链接，你得到序列A081578 ，它被描述为“Pascal-（1,3,1）数组”，这完全有意义 – 如果你旋转矩阵，那么0,0元素位于顶部，元素形成一个三角形，然后你得到1*左元素， 3*上面的元素， 1*右元素。

现在的问题是实现用于生成数字的公式。

不幸的是，这说起来容易做起来难。 例如，页面上给出的公式：

T（n，k）= sum {j = 0..n，C（k，jk）* C（n + kj，k）* 3 ^（jk）}

这是错误的，需要花一点时间阅读论文 （链接在页面上）来计算出正确的公式。 你想要的部分是命题26，推论28.在命题13之后，表2中提到了序列。注意r=4

在命题26中给出了正确的公式，但在那里也有一个错字：/。 总和中的k=0应为j=0 ：

其中T是包含系数的三角矩阵。

OEIS页面确实提供了几个实现来计算数字，但它们都不在java中，并且它们都不能轻易转录为java：

有一个mathematica示例：

 Table[ Hypergeometric2F1[-k, kn, 1, 4], {n, 0, 10}, {k, 0, n}] // Flatten 

这一直都是荒谬的简洁。 还有一个Haskell版本，同样简洁：

 a081578 nk = a081578_tabl !! n !! k a081578_row n = a081578_tabl !! n a081578_tabl = map fst $ iterate (\(us, vs) -> (vs, zipWith (+) (map (* 3) ([0] ++ us ++ [0])) $ zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 1]) 

我知道你在java中这样做，但是我不能把我的答案转录成java（对不起）。 这是一个python实现：

 from __future__ import division import math # # Helper functions # def cache(function): cachedResults = {} def wrapper(*args): if args in cachedResults: return cachedResults[args] else: result = function(*args) cachedResults[args] = result return result return wrapper @cache def fact(n): return math.factorial(n) @cache def binomial(n,k): if n < k: return 0 return fact(n) / ( fact(k) * fact(nk) ) def numerator(i,j): """ Naive way to calculate numerator """ if i == j == 0: return 0 elif i == 0 or j == 0: return 3**(max(i,j)-1) else: return numerator(i-1,j) + numerator(i,j-1) + 3*numerator(i-1,j-1) def denominator(i,j): return 3**(i+j-1) def A081578(n,k): """ http://oeis.org/A081578 """ total = 0 for j in range(n-k+1): total += binomial(k, j) * binomial(nk, j) * 4**(j) return int(total) def diff(i,j): """ Difference between the numerator, and the denominator. Answer will then be 1-diff/denom. """ if i == j == 0: return 1/3 elif i==0 or j==0: return 0 else: return A081578(j+i-2,i-1) def answer(i,j): return 1 - diff(i,j) / denominator(i,j) # And a little bit at the end to demonstrate it works. N, M = 10,10 for i in range(N): row = "%10.5f"*M % tuple([numerator(i,j)/denominator(i,j) for j in range(M)]) print row print "" for i in range(N): row = "%10.5f"*M % tuple([answer(i,j) for j in range(M)]) print row 

因此，对于封闭forms：

在哪里 只是二项式系数。

这是结果：

最后一个补充，如果你想要为大数字做这个，那么你将需要以不同的方式计算二项式系数，因为你将溢出整数。 你的答案虽然是浮点数，但由于你显然对大f(n) = T(n,n)感兴趣，我猜你可以使用斯特林的近似值。

Answer 2

对于初学者来说，这里有一些要记住的事情：

这种情况只能发生一次，但每次循环都会测试它。

 if (x == 0 && y == 0) { matrix[x][y] = 0; } 

你应该改为： matrix[0][0] = 0; 在你进入第一个循环并将x设置为1之前。因为你知道x永远不会是0你可以删除第二个条件的第一部分x == 0 ：

 for(int x = 1; x <= i; x++) { for(int y = 0; y <= j; y++) { if (y == 0) { matrix[x][y] = 1; } else matrix[x][y] = (matrix[x-1][y] + matrix[x-1][y-1] + matrix[x][y-1])/3; } } 

声明行和列没有意义，因为您只使用一次。 double[][] matrix = new double[i+1][j+1];

Answer 3

该算法的最小复杂度为Ω(n)因为您只需要将矩阵的第一列和第一行中的值与某些因子相乘，然后将它们相加。 这些因素源于n次递归递归。

但是，您需要进行递归的展开。 它本身具有O(n^2)的复杂性。 但是通过平衡展开的展开和评估，您应该能够将复杂度降低到O(n^x) ，其中1 <= x <= 2 。 这与矩阵 - 矩阵乘法的算法类似，其中朴素情况具有O(n^3)的复杂度，但Strassens的算法例如是O(n^2.807) 。

另一点是原始公式使用1/3的因子。 由于这不能通过定点数或iee 754浮点精确表示，因此在连续评估递归时误差增加。 因此，展开递归可以提供更高的准确性作为一个很好的副作用。

例如，当你展开递归sqr(n)次时，你有复杂度O((sqr(n))^2+(n/sqr(n))^2) 。 第一部分用于展开，第二部分用于评估大小为n/sqr(n)的新矩阵。 新的复杂性实际上可以简化为O(n) 。

Answer 4

为了描述时间复杂度，我们通常使用一个大的O符号。 重要的是要记住它只描述了输入时的增长。 O（n）是线性时间复杂度，但它没有说明当我们增加输入时，时间增长的速度有多快（或慢慢）。 例如：

 n=3 -> 30 seconds n=4 -> 40 seconds n=5 -> 50 seconds 

这是O（n），我们可以清楚地看到n的每次增加都会使时间增加10秒。

 n=3 -> 60 seconds n=4 -> 80 seconds n=5 -> 100 seconds 

这也是O（n），即使每n需要两倍的时间，并且每增加n的时间增加20秒，时间复杂度线性增长。

因此，如果你有O（n * n）时间复杂度并且你将执行的操作数量减半，那么你将获得等于O（n * n）的O（0.5 * n * n） – 即你的时间复杂度赢了不要改变。

这是理论，在实践中，操作的数量有时会产生影响。 因为你有一个网格n乘n，你需要填充n * n个单元格，所以你可以实现的最佳时间复杂度是O（n * n），但是你可以做一些优化：

• 网格边缘上的单元可以填充在单独的循环中。 目前在大多数情况下，你有两个不必要的条件，i和j等于0。
• 你的网格有一条对称线，你可以用它来计算它的一半，然后将结果复制到另一半。 对于每个i和j grid[i][j] = grid[j][i]

最后要注意的是，代码的清晰度和可读性比性能更重要 – 如果您可以阅读和理解代码，您可以更改代码，但如果代码太难以让您无法理解，则无法对其进行优化。 这就是为什么我只做第一次优化（它也增加了可读性），但不会做第二次 – 它会使代码更难理解。

根据经验，不要优化代码，除非性能确实导致问题。 正如威廉沃尔夫所说：

更多的计算罪是以效率的名义（不一定实现它）而不是任何其他单一原因 – 包括盲目的愚蠢。

编辑：

我认为有可能以O（1）复杂度实现此function。 虽然当您需要填充整个网格时它没有任何好处，但是O（1）时间复杂度可以立即获得任何值而无需网格。

一些观察：

• 分母等于3 ^ (i + j - 1)
• 如果i = 2或j = 2，则分子比分母小1

编辑2：

分子可以用以下函数表示：

 public static int n(int i, int j) { if (i == 1 || j == 1) { return 1; } else { return 3 * n(i - 1, j - 1) + n(i - 1, j) + n(i, j - 1); } } 

与原始问题非常相似，但没有除法，所有数字都是整数。

Answer 5

如果问题是关于如何输出函数的所有值0<=i ， 0<=j ，这里是时间O(N²)和空间O(N) 。 时间行为是最佳的。

 Use a temporary array T of N numbers and set it to all ones, except for the first element. Then row by row, use a temporary element TT and set it to 1, then column by column, assign simultaneously T[I-1], TT = TT, (TT + T[I-1] + T[I])/3. 

Answer 6

感谢will（第一）的答案，我有这个想法：

考虑到任何正解都只来自x和y轴的1。 对f每个递归调用将解决方案的每个组成部分除以3，这意味着我们可以组合地总结每个1作为解决方案组件的特征方式，并将其视为“距离”（测量为多少个调用f它来自目标）作为3的负幂。

JavaScript代码：

 function f(n){ var result = 0; for (var d=n; d<2*n; d++){ var temp = 0; for (var NE=0; NE<2*nd; NE++){ temp += choose(n,NE); } result += choose(d - 1,d - n) * temp / Math.pow(3,d); } return 2 * result; } function choose(n,k){ if (k == 0 || n == k){ return 1; } var product = n; for (var i=2; i<=k; i++){ product *= (n + 1 - i) / i } return product; } 

输出：

 for (var i=1; i<8; i++){ console.log("F(" + i + "," + i + ") = " + f(i)); } F(1,1) = 0.6666666666666666 F(2,2) = 0.8148148148148148 F(3,3) = 0.8641975308641975 F(4,4) = 0.8879743941472337 F(5,5) = 0.9024030889600163 F(6,6) = 0.9123609205913732 F(7,7) = 0.9197747256986194