使用回溯的N Queen的时间复杂度？

Question

#include<stdio.h>
#include<math.h>

void printboard(int n);
void fourQueen(int k,int n);
int place(int k,int i);
int x[100];

void NQueen(int k,int n)
{
  int i;
  for(i=1;i<=n;i++)
  {
    if(place(k,i)==1)
    {     x[k]=i;
            if(k==n)
            {
                printf("Solution\n");
                printboard(n);
            }
            else
                NQueen(k+1,n);
    }
  }
}

int place(int k,int i)
{
  int j;
  for(j=1;j<k;j++)
  {
    if((x[j]==i)||abs(x[j]-i)==abs(j-k))
        return 0;
  }
  return 1;
}

void printboard(int n)
{
  int i;
  for(i=1;i<=n;i++)
    printf("%d  ",x[i]);
}

void main()
{
    int n;
    printf("Enter Value of N:");
    scanf("%d",&n);
    NQueen(1,n);
}

我认为它有时间复杂度:O(n ^ n),因为NQueen函数是递归调用的,但是这个程序可能有更严格的约束吗？那么最好的情况,最坏的情况时间复杂性.我也对place()函数感到困惑,它是O(k)并从NQueen()调用.

Answer 1

有许多优化可以提高算法的时间复杂度.

这些链接中有更多信息:

1. https://sites.google.com/site/nqueensolver/home/algorithm-results

2. https://sites.google.com/site/nqueensolver/home/algorithms/2backtracking-algorithm

Answer 2

对于您的功能T(n) = n*T(n-1) + O(n^2) ,O(N!)平均转换为时间复杂度.

Answer 3

N-QUEEN问题的时间复杂性

> O(N!)

说明:如果我们添加所有这些并将运行时间定义为T(N).然后T(N)= O(N2)+ N*T(N-1).如果使用此重复绘制递归树,则最终项将类似于n3 + n!O(1).通过Big O的定义,这可以减少到O(n!)运行时间.

Answer 4

O(n^n) 绝对是使用回溯解决 n-queens 的上限。我假设你是通过分配一个皇后列来解决这个问题的。但是，请考虑这一点 - 当您在第一列中指定皇后的位置时，您有 n 个选项，之后，您只有 n-1 个选项，因为您不能将皇后与第一个皇后放在同一行，然后n-2等等。因此，最坏情况的复杂度仍然是 O(n!) 的上限。

希望这能回答您的问题，即使我晚了将近 4 年！

Answer 5

让我们考虑一下我们的皇后是车，这意味着我们不需要处理对角线冲突。

O(N!)假设我们正在寻找是否存在任何解决方案，那么这种情况下的时间复杂度将是最坏的情况。这是一个简单的解释。

让我们举一个 N=4 的例子。

假设我们想要填充二维矩阵。X代表空缺职位，而1代表已占据职位。

一开始，答案矩阵（我们需要填充）看起来像，

X X X X
X X X X
X X X X
X X X X

让我们按行填充，这意味着将在每行中选择一个位置，然后前进到下一行。

对于第一行，由于整个矩阵中没有填充，因此我们有4 options。对于第二排，我们3 options已经取下了一排。类似地，对于第三行，我们有2 options，对于最后一行，我们只剩下1 option。

总选项 =4*3*2*1 = 24 (4!)

现在，如果我们的皇后是车，情况就是这样，但因为我们在皇后的情况下有更多的限制。复杂性应该小于O(N!)实际操作数量。