在n x m的游戏板上检查所有可能的长度为l的线的时间复杂度是多少？
例如，井字棋盘是 3x3，线被定义为长度 3；有 8 条可能的线路。我们还可以想象一个 9x9 的棋盘和一条规则，即您需要一条长度为 5 的线才能获胜。您如何描述检查具有不同n、m和l值的每条可能线的复杂性？
请注意，这不是考虑将游戏树遍历到未来的游戏状态，只是检查棋盘的当前状态以查看当前状态是否有赢家。
问问题
160 次
1 回答
1
显然，您需要检查水平线、垂直线和对角线。
让我们假设板的布局，如果两者不相等，则 n 始终是较大的数字，并且它是侧放的“（乐高风格，而不是摩天大楼风格）。所以它是n横而m高的。
水平线将有n * (m - l)数量。
垂直线将有m * (n - l)数量。
对角线将是(m - l) * (n - l), 或m*n - l*m - l*n + l*l
如果我们假设n >= m > l，那么我们可以肯定地说它在 内O(n^2)，正如我们对二维板所期望的那样。
我们知道这l > n >= m不会有任何结果。如果n = m = l我们有一个常数（2*n + 2）。如果n = l > m我们还有更好的情况，因为我们不必检查对角线或垂直线，您只需检查m线条。如果n > l > m，那么我们可以再次排除垂直线，但必须考虑对角线。无论如何，它比做对角线、垂直和水平线要少。
但是，可以根据phant0m 的注释进行优化。它要求你知道最后一步是什么。
您可以放心地假设，如果采取了行动，那么它是在棋盘上没有赢家的时候做出的。因此，如果在棋盘上出现了一个获胜条件，那么它一定是由于最近的棋步而形成的。因此，给定此信息的最坏情况是获胜线是由最后的最新动作形成的。因此，您需要检查l - 1在每个方向（水平、垂直、前向对角线和后向对角线）延伸的 4 条线段。这是一共4 * (2*l - 1)，安然无恙O(l)。考虑到您只需要存储一个额外的坐标（最近的移动），这是一个最明智的优化。
于 2012-09-26T19:58:23.703 回答