使用回溯生成所有可能排列的时间复杂度（2 种解决方案的比较）
Time complexity of generating all possible permutations using backtracking (comparison of 2 solutions)
方法一：
https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ 在这里，我们可以看到递归方程为 T(N) = N * T(N-1) + c 所以最终的时间复杂度为 = O(N!) , 这是有道理的。
方法二：
此代码与方法 1 之间的区别在于我们每次都在做一些无用的工作（当 chosen[i] 为真时，我们继续而不是向下移动递归树）。
我认为，这里的递归关系应该是 T(N) = N * T(N-1) + N * c 因为我们可以将 for 循环分为两部分：我们在每次迭代中做持续工作的部分 (N * c ) 和一个我们进行递归调用的地方 (N * T(N-1))。然后对于 T(N-1) = (N-1) * T(N-2) + N*c （请注意，我们仍然在这里支付 N * c 成本）等等。最后，我们将剩下一个 N^N 项，对于大 N，它将支配 O(N!)。这是否意味着第二个代码片段的时间复杂度是 O(N^N) 而不是 O (N!)?
关系问题：
对于 N 皇后问题，我们有一个回溯解决方案（可以参考 https://dev.to/chengmuy/optimizing-an-n-queens-solution-3m1m）但是在这里，我们有一个 for 循环来检查当前状态是否安全（在 O(1) 平均时间内）并进行递归调用因此。除非我错了，否则这个回溯解决方案的时间复杂度也是 O(N!)。但是，我很困惑我们如何考虑 O(N!) 中提前终止分支的成本，即基本上必须检查当前列的所有行（或当前行的列，取决于实现）的成本是安全的每一次。
在这两种算法中，递归函数为 {1, …, n} 排列的每个前缀输入一次。在第一个算法中，我们可以想象 for 循环的每次迭代完成的工作在递归调用中被计算在内，因为每次迭代都会有一个递归调用。所以总的工作量与可能的前缀数量成正比。由于它们不是正确的前缀，因此这包括所有排列；所以不止n！前缀全部。事实上，长度为 n-1 的前缀的数量也是 n!，所以有超过 2(n!) 个前缀，但剩余的项下降得非常快。事实证明，存在渐近 e(n!) 前缀，其中 e 是欧拉常数，大约为 2.71828。这就是 O(n!)，因为我们可以忽略常数因子。
那么第二个算法呢？我们有相同数量的递归调用，但每个不对应于完整排列的递归调用都需要扫描具有 n 个元素的 chosen 数组。这增加了 n × (e - 1) × n!。实际上，它将渐近线更改为 O((n+1)!)，它大于 O(n!)。但不如 O(nn).
方法一：
https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ 在这里，我们可以看到递归方程为 T(N) = N * T(N-1) + c 所以最终的时间复杂度为 = O(N!) , 这是有道理的。
方法二：
此代码与方法 1 之间的区别在于我们每次都在做一些无用的工作（当 chosen[i] 为真时，我们继续而不是向下移动递归树）。 我认为，这里的递归关系应该是 T(N) = N * T(N-1) + N * c 因为我们可以将 for 循环分为两部分：我们在每次迭代中做持续工作的部分 (N * c ) 和一个我们进行递归调用的地方 (N * T(N-1))。然后对于 T(N-1) = (N-1) * T(N-2) + N*c （请注意，我们仍然在这里支付 N * c 成本）等等。最后，我们将剩下一个 N^N 项，对于大 N，它将支配 O(N!)。这是否意味着第二个代码片段的时间复杂度是 O(N^N) 而不是 O (N!)?
关系问题： 对于 N 皇后问题，我们有一个回溯解决方案（可以参考 https://dev.to/chengmuy/optimizing-an-n-queens-solution-3m1m）但是在这里，我们有一个 for 循环来检查当前状态是否安全（在 O(1) 平均时间内）并进行递归调用因此。除非我错了，否则这个回溯解决方案的时间复杂度也是 O(N!)。但是，我很困惑我们如何考虑 O(N!) 中提前终止分支的成本，即基本上必须检查当前列的所有行（或当前行的列，取决于实现）的成本是安全的每一次。
在这两种算法中，递归函数为 {1, …, n} 排列的每个前缀输入一次。在第一个算法中，我们可以想象 for 循环的每次迭代完成的工作在递归调用中被计算在内，因为每次迭代都会有一个递归调用。所以总的工作量与可能的前缀数量成正比。由于它们不是正确的前缀，因此这包括所有排列；所以不止n！前缀全部。事实上，长度为 n-1 的前缀的数量也是 n!，所以有超过 2(n!) 个前缀，但剩余的项下降得非常快。事实证明，存在渐近 e(n!) 前缀，其中 e 是欧拉常数，大约为 2.71828。这就是 O(n!)，因为我们可以忽略常数因子。
那么第二个算法呢？我们有相同数量的递归调用，但每个不对应于完整排列的递归调用都需要扫描具有 n 个元素的 chosen 数组。这增加了 n × (e - 1) × n!。实际上，它将渐近线更改为 O((n+1)!)，它大于 O(n!)。但不如 O(nn).