我很好奇Python的itertools.combinations函数的时间复杂性。我做了一些搜索，似乎许多资源都声称时间复杂性是O(n！(或O(nCr(。
然而，对于当r = 1和r = n的两个极端，公式nCr分别简化为n和1。这是否意味着我们可以得出itertools.combinations的时间复杂度是O(n(的结论？
r=1和r=n(几乎(是最佳情况(实际上r=0是下极端(，而不是最差的情况。最坏的情况，至少对于组合的数量来说，是r＝n/2。因此，如果你想用n来表示复杂性，它是O(nC(n/2((或O(n×nC(n/2((，这取决于你对元组的处理。
这是否意味着我们可以得出
itertools.combinations的时间复杂度是O(n)的结论？
不，你/我们不能那样做。
考虑以下语句：
从一组n计算r值组合的算法X是
O(nCr)。
事实上，证明1任何执行上述的算法必须至少为O(nCr)是微不足道的。但我们需要检查实际代码，以确定给定的算法正是O(nCr)
您正在做的是将其中一个或两个变量设置为固定值。这有效地改变了问题。
为了说明这一点，我们可以将固定值代入上述语句；例如
从一组n中计算1个值的组合的算法X是
O(nC1)。
由于nC1是n，我们可以将其重写为：
从一组n中计算1个值的组合的算法X是
O(n)。
但请注意，此问题与原始问题不同。
简而言之。。。这并没有使原始语句无效。
请注意，(声称的(itertools.combinations是O(n!)的说法(我认为(是你的误读。什么"；源"；实际上说的是：
"获取列表的所有组合是O(n！(。由于你要做n次来获得具有不同r值的组合，所以整个算法是O(n*n！(">
我的解读是，它谈论的是Pn，而不是nCr。但无论哪种方式，它都过于模糊，无法被视为可靠的来源。
1-非正式证明。来自n的集合的r的组合的集合具有CCD_ 21元素。构造该集合需要将nCr元素添加到数据结构中。这涉及(至少(nCr内存写入。要做到这一点(至少(需要O(nCr)时间。。。假设一台(现实世界(计算机的内存带宽有上限