首页 > 试题广场 >

n皇后最坏情况下的时间复杂度为：（）

[单选题]
n皇后最坏情况下的时间复杂度为：（） 
  • O(n)
  • O(n^2)
  • O(n^n)
  • O(n^3)
查看正确选项
添加回答
天涯咫尺头像 天涯咫尺
一个n*n的棋盘，要在上面放n个皇后。规则：两个皇后之间如果是同列、同行、同对角线它们会互相攻击。也就是说：棋盘上的任意两个皇后皇后
不能为同列、同行、同对角线。
对于这个问题、当n不大的时候，可以用穷举法实现。对于n皇后，每一行有n个位置可以放，一共n行。就会有n的n次方种情况。对于这些情况、再一一判断是不是满足情况。
发表于 2017-08-14 10:37:07 回复(2)
乐砂头像 乐砂
回溯法的话，应该不是哦o（n！），因为是一棵完全n叉树，感觉是o（n^n）
非递归算法的话是O（n！）
发表于 2020-08-18 13:01:23 回复(0)
提交观点

问题信息

复杂度
来自：乐视2017秋招开发工...
上传者：牛100
难度：
2条回答 11175浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号