trominoes 算法的复杂度

Question

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

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

平铺问题

– 输入：一个 n x n 的方板，其中一个是 1 x 1 的方块缺失，其中 n = 2k 对于某些 k ≥ 1。

– 输出：使用 tromino 的棋盘平铺，三方块通过从 2 x 2 中删除右上角 1 x 1 获得正方形。

– 您可以旋转 tromino 来平铺棋盘。基本情况：可以平铺一个 2 x 2 的正方形。

归纳：

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

– 将 tromino 放在“中心”，而 tromino 没有将 n/2 与 n/2 正方形重叠，之前 1 乘 1 地漏掉了正方形。

– 通过 n/2 板归纳地解决四个 n/2 中的每一个。

Answer 1

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

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

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

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

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

这求解为 O(N) = O(n²)，证实了上述结果。

希望对您有所帮助！

Answer 2

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

T(2) = c

其中 c 是常数，

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

其中 b 是放置 tromino 的常量。使用 master theorem，运行时绑定是

O(n^2)

通过案例 1。

Answer 3

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

– Place the tromino at the “center”, where the tromino does not overlap the n/2 by n/2 square which was earlier missing out 1 by 1 square.

我猜这是一个 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)而是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)。

Answer 4

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

trominoes 算法的复杂度

Complexity of trominoes algorithm

algorithm

time-complexity

complexity-theory

master-theorem