如何用逐步分析法识别递归回溯算法的时间和空间复杂度

Question

public class Solution {
    public int NumWays { get; set; }
    public int TotalNQueens(int n) {
        if (n <= 0)
        {
            return 0;
        }
        
        NumWays = 0;
        
        bool[][] board = new bool[n][];
        for (int i = 0; i < board.Length; i++)
        {
            board[i] = new bool[n];
        }
        
        Solve(n, board, 0);
        
        return NumWays;
    }
    
    private void Solve(int n, bool[][] board, int row)
    {
        if (row == n)
        {
            // Terminate since we've hit the bottom of the board
            NumWays++;
            return;
        }
        
        for (int col = 0; col < n; col++)
        {
            if (CanPlaceQueen(board, row, col))
            {
                board[row][col] = true; // Place queen
                Solve(n, board, row + 1);
                board[row][col] = false; // Remove queen
            }
        }
    }
    
    private bool CanPlaceQueen(bool[][] board, int row, int col)
    {
        // We only need to check diagonal-up-left, diagonal-up-right, and straight up. 
        // this is because we should not have a queen in a later row anywhere, and we should not have a queen in the same row
        for (int i = 1; i <= row; i++)
        {
            if (row - i >= 0 && board[row - i][col]) return false;
            if (col - i >= 0 && board[row - i][col - i]) return false;
            if (col + i < board[0].Length && board[row - i][col + i]) return false;
        }
        
        return true;
    }
}

Answer 1

首先，递归回溯算法不一定都在o（n！）中：当然，这取决于html" target="_blank">算法，而且可能更糟。话虽如此，一般的方法是写下时间复杂度t(n)的递推关系，然后试图求解它或至少刻画它的渐近行为。

我们感兴趣的是最坏的情况、最好的情况还是平均的情况？输入参数是什么？

在本例中，假设我们要分析最坏情况下的行为，并且相关的输入参数是solve方法中的n。

private void Solve(int n, bool[][] board, int row)
    {
        if (row == n) // base case
        {
           [...] // O(1)
           return;
        }
        
        for (...) // loop n times
        {
            if (CanPlaceQueen(board, row, col)) // O(k)
            {
                [...] // O(1)
                Solve(n, board, row + 1); // recurse on k - 1 = n - (row + 1)
                [...] // O(1)
            }
        }
    }

T(0) = 1         // base case
T(k) = k *       // loop n times 
       (O(k) +   // if (CanPlaceQueen(...))
       T(k-1))   // Solve(n, board, row + 1)
     = k T(k-1) + O(k)

T(n) = n T(n-1) + f(n)

T(n) = n!(T(0) + Sum { f(i)/i!, for i = 1..n })

我们可以通过归纳很容易地证明：

T(n) = n T(n-1) + f(n)                                          // by def.
     = n((n-1)!(T(0) + Sum { f(i)/i!, for i = 1..n-1 })) + f(n) // by ind. hypo.
     = n!(T(0) + Sum { f(i)/i!, for i = 1..n-1 }) + f(n)/n!)
     = n!(T(0) + Sum { f(i)/i!, for i = 1..n })                 // qed

现在，我们不需要精确解；我们只需要当n接近无穷大时的渐近行为。

让我们来看看无穷级数

Sum { f(i)/i!, for i = 1..infinity }

L = lim { | (f(n+1)/(n+1)!) / (f(n)/n!) |, for n -> infinity }
  = lim { | f(n+1) / (f(n)(n+1)) |, for n -> infinity }
  = 0  // if f is a polynomial
  < 1, and hence the series converges

T(n) -> n!(T(0) + Sum { f(i)/i!, for i = 1..infinity })
      = T(0) n!, if f is a polynomial

T(n) ∈ Θ(n!)

对于不同形式的递归关系的类似分析，请参见此处。

我在代码的注释中犯了一个错误（我将留下它，因为它仍然有指导意义）。实际上，循环和循环中所做的工作并不依赖于k=n-row，而是依赖于初始值n（为了清楚起见，我们将其称为n0）。

所以递推关系变成

T(k) = n0 T(k-1) + n0

T(k) = n0^k (T(0) + Sum { n0^(1-i), for i = 1..k })

T(k) = k^k (T(0) + Sum { n0^(1-i), for i = 1..k })
     ∈ Θ(k^k)