我有一个带有两个嵌套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);
}
假设您使用长度为permutatePersons
的列表调用N
,则以下递归适用:
T(N) = T(N-1) + O(N^2)
这是因为在每个递归步骤中,您使用长度为N-1的列表调用函数(其中N为当前长度),并且您还要计算总复杂度O(N ^ 2)(外部循环O(N) - 正好遍历列表和内部循环遍历O(N)-O(1)中的每个元素和总N元素的哈希映射,因此嵌套循环总体为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)
因为你有两个嵌套循环,所以你有O(m*n)
的运行时复杂性。这是因为对于n
中的Person
-deepCopyPersonSet
s,你迭代m
次。本例中的n
是Person
中personList
s的数量。
你的代码基本上是:
for(int i = 0, i < m, i++)
for(int j = 0, j < n, j++)
//your code
对于m的每次迭代,我们有n次迭代的代码
看起来它对于嵌套循环来说是n ^ 2的大O:
for(Person lPerson : personList) {
for(Person sPerson : deepCopyPersonSet) {
Person uniquePerson = CombinePeople.combine(lPerson, sPerson);
personSet.add(uniquePerson);
}
}
您必须遍历集合中每个元素的每个元素。
然后递归调用有一个很大的O,因为它会为集合中的每个元素调用一次方法。
结合这两个:n * n^2
将导致n ^ 3的大O.