algorithm - 有效地确定电子表格中行之间的关系

Question

这是我刚刚遇到的一个问题，或者更确切地说，它是一个捕获核心问题的简化。

假设我有一个电子表格，其中包含许多列，每列都带有标签，还有许多行。

我想确定何时可以从另一列中的值推断出一列中的值。例如，我们可能会发现，每当 a 列中出现“1”时，d 列中总会出现“5”，但每当“2”出现在a 列，a 3 总是出现在 d 列中。我们观察到 a 列中的值可靠地预测了 c 列中的值。

目标是识别列之间的所有此类关系。

天真的解决方案是从所有列对的列表开始，(a, b), (a, c), (a, d)... (b, c), (b, d)。 .. 等等。我们将这些称为“合格”列表。

对于这些对中的每一对，我们跟踪对中第一个的值，以及第二个中的相应值。如果我们注意到我们看到一对中的第一个值相同，但第二个值不同，则该对不再符合条件。

此过程结束时剩下的就是一组有效关系。

不幸的是，随着列数的增加，这很快变得不切实际，因为我们必须存储的数据量与列数的平方成正比。

谁能想出一个有效的方法来做到这一点？

Answer 1

我认为您无法改进 n 列的 O(n^2):考虑任何对之间不存在关系的情况。发现这一点的唯一方法是测试所有对，即 O(n^2)。