如何通过逐步分析确定时间和 space 递归回溯算法的复杂性
How to identify time and space complexity of recursive backtracking algorithms with step-by-step analysis
背景信息：我用下面的 C# 算法解决了 N 皇后问题，returns 给定大小为 n x n 的棋盘的总解数。它有效，但我不明白为什么这会是 O(n!) 时间复杂度，或者它是否是不同的时间复杂度。我也不确定递归堆栈中使用的 space （但我知道布尔锯齿数组中使用的额外 space ）。我似乎无法全神贯注地理解此类解决方案的时间和 space 复杂性。掌握这种理解在技术面试中特别有用，可以在没有能力 运行 编码的情况下进行复杂性分析。
初步调查：我读过几篇 SO 帖子，其中作者直接要求社区提供他们算法的时间和 space 复杂度。我不想做同样的事情并寻求快速简单的答案，而是想了解如何计算回溯算法的时间和 space 复杂度，以便我可以继续前进。
我还在 SO 内外的许多地方读到，一般来说，递归回溯算法是 O(n!) 时间复杂度，因为在 n 次迭代中的每一次迭代中，你都会少看一个项目：n，然后 n - 1，然后是 n - 2，... 1。但是，我还没有找到任何关于为什么会这样的解释。对于此类算法的 space 复杂性，我也没有找到任何解释。
问题：有人可以解释逐步解决问题的方法来确定时间和 space 递归回溯算法的复杂性吗？
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;
}
}
首先，递归回溯算法都在O(n!)中肯定是不正确的：当然这取决于算法，而且很可能更糟。话虽如此，一般的方法是写下时间复杂度 T(n) 的递推关系，然后尝试求解它或至少表征其渐近行为。
第 1 步：使问题精确
我们对最坏情况、最好情况还是平均情况感兴趣？输入参数是什么？
在这个例子中，假设我们要分析最坏情况下的行为，相关的输入参数是Solve方法中的n。
在递归算法中，找到一个以输入参数的值开始然后随着每次递归调用递减直到达到基本情况的参数是有用的（尽管并非总是可能）。
在这个例子中，我们可以定义k = n - row。因此，对于每次递归调用，k 都会从 n 开始递减到 0。
第 2 步：注释和剥离代码
不，我们查看代码，将其剥离到只包含相关位并使用复杂性进行注释。
我们可以将您的示例归结为以下内容：
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)
}
}
}
第 3 步：写下递推关系
这个例子的递归关系可以直接从代码中读出：
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 }
在我们的例子中，f(n) = O(n)，但让我们看看更一般的情况，其中 f(n) 是 n 中的 任意多项式 （因为事实证明这真的无关紧要）。很容易看出级数收敛，使用 ratio test:
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
因此，对于n -> infinity，
T(n) -> n!(T(0) + Sum { f(i)/i!, for i = 1..infinity })
= T(0) n!, if f is a polynomial
第 5 步：结果
由于T(n)的极限是T(0) n!，我们可以写成
T(n) ∈ Θ(n!)
这是算法最坏情况复杂度的严格限制。
此外，我们已经证明除了递归调用之外，您在 for 循环中做了多少工作并不重要，只要它是多项式的，复杂性就保持 Θ(n!)（对于这种形式的递归关系）。（粗体是因为有很多 SO 答案都弄错了。）
对于具有不同形式的递推关系的类似分析，请参阅 here。
更新
我在代码的注释上写错了（我会保留它，因为它仍然具有指导意义）。实际上，循环和循环内完成的工作都不依赖于 k = n - row，而是依赖于 initial 值 n（我们称之为 n0说清楚）。
所以递归关系变为
T(k) = n0 T(k-1) + n0
其精确解是
T(k) = n0^k (T(0) + Sum { n0^(1-i), for i = 1..k })
但由于最初 n0 = k，我们有
T(k) = k^k (T(0) + Sum { n0^(1-i), for i = 1..k })
∈ Θ(k^k)
比Θ(k!)差一点。
背景信息：我用下面的 C# 算法解决了 N 皇后问题，returns 给定大小为 n x n 的棋盘的总解数。它有效，但我不明白为什么这会是 O(n!) 时间复杂度，或者它是否是不同的时间复杂度。我也不确定递归堆栈中使用的 space （但我知道布尔锯齿数组中使用的额外 space ）。我似乎无法全神贯注地理解此类解决方案的时间和 space 复杂性。掌握这种理解在技术面试中特别有用，可以在没有能力 运行 编码的情况下进行复杂性分析。
初步调查：我读过几篇 SO 帖子，其中作者直接要求社区提供他们算法的时间和 space 复杂度。我不想做同样的事情并寻求快速简单的答案，而是想了解如何计算回溯算法的时间和 space 复杂度，以便我可以继续前进。
我还在 SO 内外的许多地方读到，一般来说，递归回溯算法是 O(n!) 时间复杂度，因为在 n 次迭代中的每一次迭代中，你都会少看一个项目：n，然后 n - 1，然后是 n - 2，... 1。但是，我还没有找到任何关于为什么会这样的解释。对于此类算法的 space 复杂性，我也没有找到任何解释。
问题：有人可以解释逐步解决问题的方法来确定时间和 space 递归回溯算法的复杂性吗？
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;
}
}
首先，递归回溯算法都在O(n!)中肯定是不正确的：当然这取决于算法，而且很可能更糟。话虽如此，一般的方法是写下时间复杂度 T(n) 的递推关系，然后尝试求解它或至少表征其渐近行为。
第 1 步：使问题精确
我们对最坏情况、最好情况还是平均情况感兴趣？输入参数是什么？
在这个例子中，假设我们要分析最坏情况下的行为，相关的输入参数是Solve方法中的n。
在递归算法中，找到一个以输入参数的值开始然后随着每次递归调用递减直到达到基本情况的参数是有用的（尽管并非总是可能）。
在这个例子中，我们可以定义k = n - row。因此，对于每次递归调用，k 都会从 n 开始递减到 0。
第 2 步：注释和剥离代码
不，我们查看代码，将其剥离到只包含相关位并使用复杂性进行注释。
我们可以将您的示例归结为以下内容：
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)
}
}
}
第 3 步：写下递推关系
这个例子的递归关系可以直接从代码中读出：
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 }
在我们的例子中，f(n) = O(n)，但让我们看看更一般的情况，其中 f(n) 是 n 中的 任意多项式 （因为事实证明这真的无关紧要）。很容易看出级数收敛，使用 ratio test:
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
因此，对于n -> infinity，
T(n) -> n!(T(0) + Sum { f(i)/i!, for i = 1..infinity })
= T(0) n!, if f is a polynomial
第 5 步：结果
由于T(n)的极限是T(0) n!，我们可以写成
T(n) ∈ Θ(n!)
这是算法最坏情况复杂度的严格限制。
此外，我们已经证明除了递归调用之外，您在 for 循环中做了多少工作并不重要，只要它是多项式的，复杂性就保持 Θ(n!)（对于这种形式的递归关系）。（粗体是因为有很多 SO 答案都弄错了。）
对于具有不同形式的递推关系的类似分析，请参阅 here。
更新
我在代码的注释上写错了（我会保留它，因为它仍然具有指导意义）。实际上，循环和循环内完成的工作都不依赖于 k = n - row，而是依赖于 initial 值 n（我们称之为 n0说清楚）。
所以递归关系变为
T(k) = n0 T(k-1) + n0
其精确解是
T(k) = n0^k (T(0) + Sum { n0^(1-i), for i = 1..k })
但由于最初 n0 = k，我们有
T(k) = k^k (T(0) + Sum { n0^(1-i), for i = 1..k })
∈ Θ(k^k)
比Θ(k!)差一点。