c - N皇后使用回溯的时间复杂度？

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 函数是递归调用的，但是这个程序是否有更严格的界限？最好情况和最坏情况的时间复杂度如何。我也对复杂度为 O(k) 并从 NQueen() 调用的 place() 函数感到困惑。

Answer 1

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

这些链接中有更多信息:

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

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