棋盘覆盖空间复杂度推导

棋盘覆盖问题是一个经典的算法问题，通常用于展示递归算法的思想。假设我们有一个如下的棋盘：


其中某一个方格被移除掉。现在我们需要用L形大小的平板覆盖整个棋盘，如图：


我们可以将棋盘划分为4个相等的部分，其中每个部分最中心的方格是被移除的方格，因此我们需要在剩余的方格上做覆盖。

对于每一个部分，我们都可以分别用一个 L 形的平板进行覆盖，如下图所示：


之后我们就得到了如下的覆盖方案：


接下来我们可以按照上述过程进行递归，不断将棋盘缩小为 1/2 的面积，直到我们无法再进行递归为止。

对于空间复杂度的推导，由于我们采用的是递归算法，所以我们需要考虑递归栈的空间复杂度。对于这个问题，我们可以采取自顶向下的方式递归求解，因此递归栈的高度即为递归的层数。

假设原始的棋盘大小为 $2^k \times 2^k$，则我们需要不断将棋盘缩小为 $2^{k-1} \times 2^{k-1}$，$2^{k-2} \times 2^{k-2}$，$2^{k-3} \times 2^{k-3}$……$2^{1} \times 2^{1}$。

因此，空间复杂度为 $O(k)$，其中 $k$ 是递归的层数，即 $\log_2 n$，其中 $n=2^k$ 为原始棋盘的大小。

值得一提的是，虽然递归算法的空间复杂度对于大多数的计算机系统来说都非常的可行，但仍然有可能在递归深度很大的时候导致栈溢出的问题。因此，在实际应用中，我们需要对递归算法进行优化或使用非递归算法来解决问题。