棋盘覆盖分治法时间复杂度

棋盘覆盖问题使用分治算法可以在 $O(n^2)$ 的时间复杂度内求解，其中 $n$ 是棋盘边长。具体地，分治算法的时间复杂度可以用递推式表示为：

$T(n) = 4T\left(\dfrac{n}{2}\right) + O(n^2)$

其中 $4T\left(\dfrac{n}{2}\right)$ 表示将一个边长为 $n$ 的棋盘分成四个边长为 $\dfrac{n}{2}$ 的子棋盘后分别求解覆盖问题的时间复杂度，$O(n^2)$ 表示合并四个子棋盘的复杂度。

根据主定理（Master Theorem），我们可以得到该递推式的解为 $O(n^2)$。因此，棋盘覆盖问题使用分治算法的时间复杂度为 $O(n^2)$。