经典n-皇后回溯算法的时间复杂度分析

Question

我一直在读一些解决经典的n皇后问题的代码。它只是为了找到一个解决方案(不是所有的解决方案或计算解决方案的#)。您可以在极客健忘网站上找到完整的代码，总结如下。问题是，这段代码的时间复杂度是多少，真正的

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    /* Check this row on left side */
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    /* Check upper diagonal on left side */
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return false;

    /* Check lower diagonal on left side */
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    /* base case: If all queens are placed
      then return true */
    if (col >= N)
        return true;

    /* Consider this column and try placing
       this queen in all rows one by one */
    for (int i = 0; i < N; i++)
    {
        /* Check if queen can be placed on
          board[i][col] */
        if ( isSafe(board, i, col) )
        {
            /* Place this queen in board[i][col] */
            board[i][col] = 1;

            /* recur to place rest of the queens */
            if ( solveNQUtil(board, col + 1) )
                return true;

            /* If placing queen in board[i][col]
               doesn't lead to a solution, then
               remove queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK
        }
    }

     /* If queen can not be place in any row in
        this colum col  then return false */
    return false;
}

/* This function solves the N Queen problem using
   Backtracking. It mainly uses solveNQUtil() to
   solve the problem. It returns false if queens
   cannot be placed, otherwise return true and
   prints placement of queens in the form of 1s.
   Please note that there may be more than one
   solutions, this function prints one  of the
   feasible solutions.*/
bool solveNQ()
{
    int board[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if ( solveNQUtil(board, 0) == false )
    {
      printf("Solution does not exist");
      return false;
    }

    printSolution(board);
    return true;
}

如果你回顾一下评论的历史，有人说它是O(n!)，甚至是指数。但我认为这两种观点都不正确。

例如，为了O(n!)的主张，有人给了T(n)= n*(T(n-1) + O(n))，这导致了O(n!)。

为什么我认为这是错误的(不是O(n!)**)?**

1.问题是，for循环在solveNQUtil中总是运行N时间。它不会随着问题范围n的减少而减少。因此，上述公式中的乘数n是不正确的。应该用一个固定的数字N来代替它。

2.col在isSafe中沿递归树增加，这意味着isSafe中的for循环具有越来越多的迭代次数。迭代的#是N - n。

因此，基本上，递归应该是T(n)= N *(T(n-1) + O(N - n)) (N是固定的)。不知道如何解决这个问题，但至少应该是O(N^N)。有什么想法吗？

递归树法

如果使用递归树，则会有不同的O(n^n)路径一直到叶子，每个路径都会执行O(1+2+..n)操作进行冲突检查。所以总时间应该是O(n^(n+2))。是这样的吗？

有人能指出这是否正确，并给出适当的理由吗？

Answer 1

这是一个很好的观察。让我对这些步骤进行很多思考和模拟。

只看代码并试图导出复杂性，您实际上是正确的，它应该是O(n^n)。

但问题是，尽管solveNQUtil中的内循环运行了N次，但递归函数solveNQUtil没有被调用N次。在最坏的情况下，它将被称为n-1时间。因为前面的每个列都有一个皇后作为它们，所以当这些列被迭代时，一行将从进一步的考虑中删除。所以不要再重复了

T(n)= N *(T(n-1))

它确实是间接的

T(n)= n *(T(n-1))

Answer 2

注：-请记住，我们正在计算最坏情况下的时间复杂度。

函数solveNQUtil()使用for循环，其范围为“n”，它将调用自身(n-1)倍，以填充所有行。此外，我们使用一个函数isSafe()来检查皇后在特定位置是否安全。

得到了一个递推关系T(n) = n*T(n-1) +O(N)，其中T(0) = O(1)

O()< O(N)

因此，递推关系是T(n) = n*T(n-1) + O(N)。

T(n-1) = (n-1)*T(n-2) + O(N)

T(n-2) = (n-2)*T(n-3) + O(N)

T(n-3) = (n-3)*T(n-4) + O(N)

。。

。。

。。

。。

。。

。。

。。

T(+1)=(+1)*T()+ O(N)

因此，T(n) =n*(n-1)(n-2)(n-3).(N+1)_T(n--1)+ k_O(N)

如果是k=n

T(n) = n!_T(0) + n_O(N)

T(n) = n！+ O(N^2)

因此，T(n) = O(n!)

希望它对你有帮助，也可能是别人