这是来自一个古老的奥林匹克练习题:
假设您有一个 1000x1000 的网格，其中单元格 (i,j) 包含数字 i*j。 (行和列从 1 开始编号。)
在每一步，我们从旧网格构建一个新网格，其中每个单元格 (i,j) 包含最后一个网格中 (i,j) 的“邻域平均值”。 “邻域平均值”定义为像元及其最多 8 个邻域的平均值的下限。例如，如果网格角落的 4 个数字是 1、2、5、7，在下一步中，角落将计算为 (1+2+5+7)/4 = 3。
最终我们将达到所有数字都相同并且网格不再改变的点。目标是弄清楚达到这一点需要多少步骤。
我尝试简单地模拟它，但这不起作用，因为答案似乎是 O(n^2) 步，每个模拟步骤都需要 O(n^2) 来处理，结果是 O(n^4)对于 n=1000 来说太慢了。
有没有更快的方法来做到这一点？
最佳答案
“地板”步骤让我怀疑不太可能有分析解决方案，这实际上是一个微观优化练习。这是我的想法。
让我们暂时忽略角落和边缘。他们只有3996个，无论如何他们都需要特殊对待。
对于内部单元格，您需要添加 9 个元素以获得其下一个状态。但是反过来说:每个内部单元格都必须是 8 个附加单元的一部分。
或者是吗？从三个连续的行 A[i] 、 B[i] 和 C[i] 开始，并计算三个新行:
A'[i] = A[i-1] + A[i] + A[i+1]
B'[i] = B[i-1] + B[i] + B[i+1]
C'[i] = C[i-1] + C[i] + C[i+1]
(请注意，由于
A'[i+1] = A'[i] - A[i-1] + A[i+1] ，您可以使用“滑动窗口”稍微更快地计算每一个。相同数量的算术运算但更少的负载。)现在，要在
B[j] 位置获取新值，您只需计算 A'[j] + B'[j] + C'[j] 。到目前为止，我们还没有保存任何工作；我们刚刚对添加的内容进行了重新排序。
但是现在，计算更新后的行
B ，您可以丢弃 A' 并计算下一行:D'[i] = D[i-1] + D[i] + D[i+1]
...您可以使用数组
B' 和 C' 来计算行 C 的新值，而无需重新计算 B' 或 C' 。 (当然，您可以通过将行 B' 和 C' 移动为 A' 和 B' 来实现这一点……但这种方式更容易解释。也许吧。我想。)对于每一行，比如说
B ，我们扫描它一次以产生 B' 做 2n 算术运算，第二次计算更新的 B 也需要 2n 运算，所以我们总共对每个元素进行四次加法/减法，而不是八次。当然，在实践中，您会在更新
C' 的同时计算 B 以实现相同数量的操作但更好的局部性。这是我唯一的结构性想法。 SIMD 优化专家可能有其他建议...
关于algorithm - 模拟矩阵运算的快速方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24101774/