具有嵌套for循环的递归算法的大O时间复杂度

Question

我有一个带有两个嵌套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);
}

Answer 1

假设您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)