java 评估生成N个数的K个组合的算法的时间和空间复杂度

2nbm6dog  于 2022-12-28  发布在  Java
关注(0)|答案(1)|浏览(155)

我正在解决一个Leetcode的77题叫做"组合"。下面是问题陈述:
给定两个整数nk,返回从[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;
    }
}

虽然这段代码运行得非常好,但是我仍然在评估这个算法的时间和空间复杂度。
上述解决方案的时间和空间复杂度是多少?

svmlkihl

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)!))

相关问题