Python O(n) 中组合的时间复杂度不是吗？
Isn't the time complexity for combinations in Python O(n)?
我很好奇 Python 的 itertools.combinations 函数的时间复杂度。我做了一些搜索，似乎很多资源都声称时间复杂度是 O(n!) or .
然而，对于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))，这取决于你对元组的处理.
Does this mean we can conclude that the time complexity of itertools.combinations is O(n)?
不，你/我们不能那样做。
考虑这个陈述：
Algorithm X to compute the combinations of r values from a set of n is O(nCr).
事实上证明1 任何 算法执行上述必须 是微不足道的] 至少 O(nCr)。但是我们需要检查实际代码以确定 given 算法 exactly O(nCr)
您正在做的是将一个或两个变量设置为固定值。这有效地 改变了问题 。
为了说明这一点，我们可以将固定值代入上述语句；例如
Algorithm X to compute the combinations of 1 value from a set of n is O(nC1).
由于 nC1 是 n，我们可以将其重写为：
Algorithm X to compute the combinations of 1 value from a set of n is O(n).
但是请注意这个问题与原来的问题不同。
简而言之...这并没有使原始声明无效。
请注意，（据称）声称 itertools.combinations 是 O(n!) 是（我认为）您的误读。该“消息来源”实际上说的是：
"Getting all combinations of a list is O(n!). Since you're doing that n times to get combinations with different values of r, the whole algorithm is O(n * n!)."
我的阅读是它在谈论 Pn 而不是 nCr。但无论哪种方式，它都太模糊了，不能被认为是可靠的来源。
1 - 非正式证明。来自一组 n 的 r 的组合集有 nCr 个元素。构建这个集合需要向数据结构中添加 nCr 个元素。这涉及（至少）nCr 内存写入。这样做需要（至少）O(nCr) 时间...假设一台（真实世界的）计算机内存带宽有上限。
我很好奇 Python 的 itertools.combinations 函数的时间复杂度。我做了一些搜索，似乎很多资源都声称时间复杂度是 O(n!) or
然而，对于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))，这取决于你对元组的处理.
Does this mean we can conclude that the time complexity of
itertools.combinationsisO(n)?
不，你/我们不能那样做。
考虑这个陈述：
Algorithm X to compute the combinations of r values from a set of n is
O(nCr).
事实上证明1 任何 算法执行上述必须 是微不足道的] 至少 O(nCr)。但是我们需要检查实际代码以确定 given 算法 exactly O(nCr)
您正在做的是将一个或两个变量设置为固定值。这有效地 改变了问题 。
为了说明这一点，我们可以将固定值代入上述语句；例如
Algorithm X to compute the combinations of 1 value from a set of n is
O(nC1).
由于 nC1 是 n，我们可以将其重写为：
Algorithm X to compute the combinations of 1 value from a set of n is
O(n).
但是请注意这个问题与原来的问题不同。
简而言之...这并没有使原始声明无效。
请注意，（据称）声称 itertools.combinations 是 O(n!) 是（我认为）您的误读。该“消息来源”实际上说的是：
"Getting all combinations of a list is O(n!). Since you're doing that n times to get combinations with different values of r, the whole algorithm is O(n * n!)."
我的阅读是它在谈论 Pn 而不是 nCr。但无论哪种方式，它都太模糊了，不能被认为是可靠的来源。
1 - 非正式证明。来自一组 n 的 r 的组合集有 nCr 个元素。构建这个集合需要向数据结构中添加 nCr 个元素。这涉及（至少）nCr 内存写入。这样做需要（至少）O(nCr) 时间...假设一台（真实世界的）计算机内存带宽有上限。