t**r
发帖数: 3428 | 1 leetcode里， backtracking的time complexity怎么算，比如permutations这题目
class Solution {
public:
void perm(vector num,int k,int n, vector > &res){
if (k==n){
res.push_back(num);
}else{
for (int i=k;i<=n;i++){
int tmp = num[k];
num[k]=num[i];
num[i]=tmp;
perm(num,k+1,n,res);
tmp = num[k];
num[k]=num[i];
num[i]=tmp;
}
}
}
vector > permute(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > res;
perm(num,0,(num.size()-1),res);
return res;
}
}; | k*******n
发帖数: 16 | 2 尝试推了一下，不知道对不对
T(n) = n * T(n - 1) + n
= n * (n - 1) * T(n - 2) + n * (n - 1) + n
= n * (n - 1) * ... * (n - k + 1) * T(n - k)
+n * (n - 1) * ... * (n - k + 1)
+ ... + n * (n - 1) + n
When k =n, T(n - k) = T(0) = 1
T(n) = (n!) + (n!) + (n!) / 2 + ... + n = O(n!) = O(n^n) | t*****3
发帖数: 112 | 3 permutation的复杂度应该是O(n!)，算法过程恰好遍历了所有的排列可能。更general
的感觉复杂度就是试探了的可能解的规模。 | s******t
发帖数: 229 | | s**x
发帖数: 7506 | 5 Where is the backtracking ？ | s****i
发帖数: 65 | 6 perm(num,k+1,n,res);
后面3句，
tmp = num[k];
num[k]=num[i];
num[i]=tmp;
原先i,k上的值换了，现在又换回来了，下一个for循环跟下一个数换
【在 s**x 的大作中提到】
: Where is the backtracking ？
|
|
