我有一个带有两个嵌套 for 循环的递归算法。我正在尝试弄清楚 Big-O 时间复杂度是多少。
public Set<Person> getDistinctCombinedPersons(Collection<Person> persons) {
return permutatePersons(new ArrayList(persons), new HashSet<>(persons));
}
private Set<Person> permutatePersons(List<Person> personList, Set<Person> personSet) {
if(personList.isEmpty() {
return personSet;
}
Set<Person> deepCopyPersonSet = new HashSet<>(personSet);
for(Person lPerson : personList) {
for(Person sPerson : deepCopyPersonSet) {
Person uniquePerson = CombinePeople.combine(lPerson, sPerson);
personSet.add(uniquePerson);
}
}
personList.remove(personList.size()-1);
return permutatePersons(personList, personSet);
}
最佳答案
假设您使用长度为 N
的列表调用 permutatePersons
,以下递归适用:
T(N) = T(N-1) + O(N^2)
那是因为在每个递归步骤中,您都调用长度为 N-1 的函数(其中 N 是当前长度),并且您还计算总复杂度 O(N^2)(外循环 O(N) - 只是遍历列表和内部循环遍历 O(N) -O(1) 中的每个元素和总 N 个元素的 HashMap ,因此嵌套循环总体为 O(N^2))。
你可以很容易地看到:
T(N) = T(N-1) + O(N^2) = T(N-2) + O(N^2) + O((N-1)^2) =...
= O(n(n+1)(2n+1)/6) = O(n^3)
关于java - 具有嵌套 for 循环的递归算法的大 O 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47212955/