n皇后问题递归算法的时间复杂度判定疑问

首先明确：递归版n皇后的时间复杂度，严格来说是O(n×n!)，但很多资料简化表述为O(n!)，这两种说法的核心逻辑是一致的，下面结合你的问题和代码拆解：

1. 决策树的核心分支数是n! #

n皇后要求每行放一个皇后，且互不攻击，所以递归的深度固定为n（对应n行）：

• 第一行有n个列可选；
• 第二行不能和第一行同列、同斜线，最多有n-1个合法列可选；
• 第三行最多有n-2个合法列可选；
• ……
• 第n行只有1个合法列可选。

所有合法的递归路径总数就是n×(n-1)×(n-2)×…×1 = n!，这就是资料里说O(n!)的核心依据——它描述的是有效搜索分支的数量。

2. 遍历所有列的操作不改变量级 #

看你贴的伪代码：

bool solveNQueens(rowIndex, matrix)
{
  // 递归终止条件

  // 遍历当前行的所有列
  for (int i = 0; i<4; i++)
  {
    if(cellAvailable) // 检查当前列是否可放置皇后
    {
      solveNQueens(rowIndex+1, matrix);
    }
  }
}

这里每行会遍历n列，但大部分列会被cellAvailable直接过滤，不会触发下一层递归。比如4皇后的场景：

• 第一行遍历4列，其中4个合法列都会进入下一层；
• 第二行每个递归调用遍历4列，但最多只有3个合法列会继续递归；
• 第三行每个递归调用遍历4列，最多只有2个合法列会继续递归；
• 第四行每个递归调用遍历4列，只有1个合法列会触发终止条件。

总循环次数是4 + 4×3 + 4×3×2 + 4×3×2×1 = 64，而4×4! = 96，两者是同量级的。也就是说，遍历所有列的操作只是给n!的量级乘以了一个系数n，最终时间复杂度是O(n×n!)——这是更严格的表述，但n!是主导项，所以很多资料会简化为O(n!)。

总结 #

• 若关注有效搜索分支数，时间复杂度可以简化为O(n!)；
• 若把每一步的列遍历和合法性检查都算进去，严格的时间复杂度是O(n×n!)；
• 你代码里的遍历操作不会让复杂度突破n!的量级，因为无效列的检查是O(1)（只要实现合理，比如用数组记录列、斜线的占用状态），不会额外增加更高阶的开销。

内容的提问来源于stack exchange，提问作者Santosh R