algorithm - 从 n 个元素生成长度为 r 的组合而不重复或排列的函数的时间复杂度是多少？

Question

以下函数接受元素列表src以及组合长度r。它打印出长度为 r 的所有可能组合，而不会重复组合内的元素或以不同顺序（排列）重复组合。

  void fn(List<dynamic> src, int r, List<dynamic> tmp) {
    for (var i = 0; i < src.length; i++) {
      tmp.add(src.removeAt(i));
      
      if (tmp.length == r) print(tmp.toString());
      
      else if (i < src.length) fn(src.sublist(i), r, tmp);
      
      src.insert(i, tmp.removeLast());
    }
  }
  

所以，给定 n = [1,2,3,4,5] 和 r = 3，它会打印出来

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

你如何用大 O 表示法描述这个函数的时间复杂度？显然， src和r的长度都必须考虑在内。如果我没记错的话，打印出所有具有重复和排列的组合的类似函数的时间复杂度将是 O(n^r)。但是在这种情况下是什么？

标签： algorithmtime-complexity

Answer 1

根据 Stef 的评论，时间复杂度似乎是O(r(n choose r))。