我正在解决一个Leetcode的77题叫做"组合"。下面是问题陈述:
给定两个整数n
和k
,返回从[1,n]
范围中选择的k
数字的所有可能组合。您可以按任何顺序返回答案。
下面是我的代码:
class Solution {
public List<List<Integer>> combine(int n, int k) {
return combine(1, new LinkedList<>(), k, new ArrayList<>(), n);
}
private List<List<Integer>> combine(int start, LinkedList<Integer> comb, int k, List<List<Integer>> result, int n){
if(k == 0){
result.add(new LinkedList<>(comb));
return result;
}
for(int i = start; i <= n-k+1; i++){
comb.add(i);
combine(i+1, comb, k-1, result, n);
comb.pollLast();
}
return result;
}
}
虽然这段代码运行得非常好,但是我仍然在评估这个算法的时间和空间复杂度。
上述解决方案的时间和空间复杂度是多少?
1条答案
按热度按时间svmlkihl1#
该算法的时间复杂度为O(k * n!/(k!*(n-k)!))**。
由于该任务的时间复杂度自然受限于来自给定的
n
元素集合 * 的 *k
-组合的数目,其可以使用二项式系数来评估:对于每一个生成的组合,我们需要构造一个大小为
k
的新的List
,所有其他成本都是常数。因此,得到的时间复杂度将是
O(k * ( n!/(k!*(n-k)!))
。由于我们需要在内存中分配所有
n!/(k!*(n-k)!)
组合,每个组合的大小为k
,并且除此之外,算法不需要额外的空间,因此空间复杂度也是O(k * ( n!/(k!*(n-k)!))
。