Redian新闻
>
leetcode里, backtracking的time complexity怎么算,比如permutations这题目
avatar
leetcode里, backtracking的time complexity怎么算,比如permutations这题目# JobHunting - 待字闺中
t*r
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;
}
};
avatar
k*n
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)
avatar
t*3
3
permutation的复杂度应该是O(n!),算法过程恰好遍历了所有的排列可能。更general
的感觉复杂度就是试探了的可能解的规模。
avatar
s*t
4
用数学公式? 高中排列组合思想
avatar
s*x
5
Where is the backtracking ?
avatar
s*i
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 ?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。