2

（分而治之）trominoes 算法的复杂性是什么或应该是什么？为什么？

我得到了一块 2^k * 2^k 大小的木板，其中一块瓷砖被随机移除，使其成为一块有缺陷的木板。任务是用“trominos”填充，这是一个由 3 个瓷砖组成的 L 形图形。

平铺问题

– 输入：一个 n × n 的正方形板，缺少一个 1 × 1 的正方形，其中对于某些 k ≥ 1，n = 2k。

– 输出：使用 tromino 的棋盘拼贴，通过从 2 x 2 正方形中删除右上角 1 x 1 角获得的三个正方形瓷砖。

– 您可以旋转 tromino，以平铺木板。基础案例：可以平铺一个 2 x 2 的正方形。

就职：

– 将正方形分成 4 个，n/2 x n/2 个正方形。

– 将tromino 放置在“中心”，tromino 不会与先前错过的 1 x 1 方块的 n/2 x n/2 方块重叠。

– 以感应方式求解四个 n/2 x n/2 板中的每一个。

4

4 回答 4

4

该算法运行时间为 O(n 2 ) = O(4 k )。要了解原因，请注意您的算法对每个网格执行 O(1) 工作，然后对宽度和高度为原始大小一半的网格进行四次子调用。如果我们使用 n 作为表示网格宽度或高度的参数，我们有以下递归关系：

T(n) = 4T(n / 2) + O(1)

根据主定理，这解决了 O(n 2 )。由于 n = 2 k，我们看到 n 2 = 4 k ，所以如果你想使用 k 作为参数，这也是 O(4 k )。

我们也可以让 N 表示棋盘上的方格总数（因此 N = n 2），在这种情况下，子调用是四个大小为 N / 4 的网格。这给出了复发

S(N) = 4S(N / 4) + O(1)

这解决了 O(N) = O(n 2 )，确认了上述结果。

希望这可以帮助！

于 2015-02-23T19:27:10.040 回答
3

我将尝试提供不太正式的解决方案，但不使用主定理。

– 将tromino 放置在“中心”，tromino 不会与先前错过的 1 x 1 方块的 n/2 x n/2 方块重叠。

我猜这是O(1)手术？在这种情况下，如果n是板尺寸：

T(1) = O(1)
T(n) = 4T(n / 4) + O(1) = 
     = 4(4T(n / 4^2) + O(1)) + O(1) = 
     = 4^2T(n / 4^2) + 4*O(1) + O(1) =
     = ... =
     = 4^kT(n / 4^k) + 4^(k - 1)*O(1)

但是n = 2^k x 2^k = 2^(2k) = (2^2)^k = 4^k，所以整个算法是O(n)。

请注意，这与@Codor 的回答并不矛盾，因为他认为n是板的边长，而我认为是整个区域。

如果中间步骤不是O(1)but O(n)：

T(n) = 4T(n / 4) + O(n) =
     = 4(4*T(n / 4^2) + O(n / 4)) + O(n) =
     = 4^2T(n / 4^2) + 2*O(n) = 
     = ... =
     = 4^kT(n / 4^k) + k*O(n)

我们有：

k*O(n) = n log n because 4^k = n

所以整个算法是O(n log n).

于 2015-02-23T19:47:36.437 回答
3

据我了解，复杂度可以确定如下。让T(n)表示求解边长 的板所需的步数n。从上面原始问题的描述中，我们有

T(2) = c

其中c是一个常数并且

T(n) = 4*T(n/2) + b

whereb是放置 tromino 的常数。使用主定理，运行时界限是

O(n^2)

通过案例 1。

于 2015-02-23T19:29:47.720 回答
0

每个放置的 tromino 做 O(1) 工作。由于要放置 (n^2-1)/3 trominos，因此该算法需要 O(n^2) 时间。

于 2015-02-23T23:23:57.577 回答