N皇后暴力算法时间复杂度分析求助：O(n²)是否正确？

首先明确：你之前认为的O(n²)是错误的，这个暴力搜索解法的时间复杂度是指数级的，远高于多项式级别。

代码执行流程拆解 #

这段代码是典型的回溯式暴力搜索：

• 从第0行开始，每一行尝试n个列的位置放置皇后
• 每选一个列，就递归进入下一行继续尝试
• 当所有行都放完皇后（row == self.n），才调用is_valid验证整个布局是否合法
• 如果某条递归路径找到合法解，会立即返回True终止搜索；否则回溯，尝试当前行的下一个列

时间复杂度分析 #

1. 递归分支数量：
   每一行有n种列选择，一共n行，因此最坏情况下（遍历所有可能的布局），总共有nⁿ种不同的皇后位置组合（递归树的叶子节点数）。
2. 验证操作的复杂度：
   当递归到最后一行时，is_valid需要检查所有皇后是否冲突。常规实现中，这需要遍历所有皇后对（共O(n²)次检查），所以单次验证的时间是O(n²)。
3. 最坏情况总复杂度：
   两者结合，最坏情况下的时间复杂度是O(nⁿ × n²)，可以简化为O(nⁿ)——因为指数项的增长速度远快于多项式项，低阶项可以忽略。

补充说明 #

• 如果存在合法解且搜索过程中较早找到，实际运行时间会比最坏情况短，但Big-O描述的是最坏场景的复杂度，因此仍以O(nⁿ)为准。
• 你之前误以为是O(n²)，可能是混淆了“遍历行的次数”和“整体搜索空间的规模”，但这里的核心是每一步都有n种分支选择，导致搜索空间呈指数级膨胀，而非线性或平方级。

内容的提问来源于stack exchange，提问作者ak.