gpt4 book ai didi

java - 如何求dfs+回溯算法的时间复杂度?

转载 作者:塔克拉玛干 更新时间:2023-11-02 08:03:00 26 4
gpt4 key购买 nike

我正在尝试在 leetcode https://leetcode.com/problems/factor-combinations/description/ 上解决这个问题

Numbers can be regarded as product of its factors. For example

8 = 2 x 2 x 2; = 2 x 4.

编写一个函数,它接受一个整数 n 并返回它的因子的所有可能组合。

虽然我能够使用 dfs 方法编写代码,但我很难在输入方面插入其最坏情况的时间复杂度。有人可以帮忙吗?

 public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> current = new ArrayList<Integer>();
getFactorsHelper(n,2,current,result);
return result;
}


public void getFactorsHelper(int n,int start,List<Integer> current, List<List<Integer>> result){
if(n<=1 && current.size()>1){
result.add(new ArrayList<>(current));
return;

}
for(int i=start;i<=n;i++){

if(n%i==0) {
current.add(i);
getFactorsHelper(n/i,i,current,result);
current.remove(current.size()-1);
}

}

}

最佳答案

我这样计算你的代码的复杂度:

让我们考虑getFactorsHelper(n,2)运行时 是函数T(n)

在下面的部分你有一个带有 i 索引的循环。

for(int i=start;i<=n;i++){    
if(n%i==0) {
current.add(i);
getFactorsHelper(n/i,i,current,result);
current.remove(current.size()-1);
}
}

n 在每次迭代中除以 i。所以我们有:

(第一次迭代)

getFactorsHelper(n/2,2,current,result) = T(n/2) 

(第二次迭代)

getFactorsHelper(n/3,3,current,result) <= getFactorsHelper(n/3,2,current,result) = T(n/3) 

(第三次迭代)

getFactorsHelper(n/4,4,current,result) <= getFactorsHelper(n/4,2,current,result) 
= T(n/4)

...

(最终迭代)

getFactorsHelper(n/n,n,current,result) <= getFactorsHelper(n/n,2,current,result) = T(n/n) = T(1) 

总成本

T(n) <= T(n/2) + T(n/3) + T(n/4) + ... + T(1)

求解递归函数

order

希望对您有所帮助。

关于java - 如何求dfs+回溯算法的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45662736/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com