Question

八皇后递归算法 求解空间复杂度

求此算法的时间复杂度和空间复杂度的计算过程！

我对递归的空间复杂度有点不明白。

函数EightQueen伪代码如下图，调用为：
EightQueen （0）；

//Out_Put_Queen() 为输出函数。

感谢各路大侠！
求解答！

Answer 1

在这里，空间复杂度并不大。因为每递归一层，只是增加一个形式变量的空间，以及递归返回地址的开销。而且在八皇后问题来说，递归深度最大为9层。若是N皇后问题，则空间复杂度也仅是O（N），且系数挺小的。所以说，在这里空间复杂度不是一个大的问题。

追问

求教时间复杂度！

追答

时间复杂度的话，它是一个穷举。8皇后的话是8*O(n)*8=O(8^3)，主要还与算法中的if 列不同||斜线不同 的方法有关。中间的O(n)用一般方法的话大约在(4n~5n)左右