您已經有了“ k個組合”的算法：給定n個項目，選擇k個項目，將排序視為無關緊要的項目。從遠古時代開始，我們知道期望有多少種組合：
n!
-----------
(n - k)! k!
對于給定的n（例如10），當k等于n（5）的一半時，該表達式將最大化。當n或k接近極限時，組合的數量將大大減少。
通過一些重組和簡化，我們可以重寫您的代碼，以便combos()在最壞的情況下對的調用次數大致等于組合的次數。有趣的是，調用次數和組合次數具有很好的對稱逆關系。
最重要的是，在最壞的情況下，兩者都受上面顯示的公式約束。這實際上是O()您所要求的范圍。但是也許不完全是因為重寫的代碼產生的子例程調用比您的代碼少，即使它們確實產生了相同的結果。下例中的短路邏輯防止了額外的調用，因此使最壞情況下的參數都能正常運行。
如果該公式是最壞情況的界限，那么您的算法是否在多項式時間內運行？在這些問題上，我比專家更直觀，但我認為答案是否定的。最糟糕的情況是when k = n / 2，它為您提供了以下簡化。盡管分母真的很快變大，但與分子的Chuck-Norris增長率相比卻相形見pale。
n!
-------------
(n/2)! (n/2)!
# For example, when n = 40.
product(1..40) product( 21..40) # Eat my dust, Homer!
----------------------------- = ---------------------
product(1..20) product(1..20) product(1..20 ) # Doh!
# Q.E.D.
關于n和k的許多值的經驗說明：
from itertools import combinations
from math import factorial
n_calls = 0
def combos(vals, size):
# Track the number of calls.
global n_calls
n_calls += 1
# Basically your algorithm, but simplified
# and written as a generator.
for i in range(0, len(vals) - size + 1):
v = vals[i]
if size == 1:
yield [v]
else:
for c in combos(vals[i+1:], size - 1):
yield [v] + c
def expected_n(n, k):
# The mathematical formula for expected N of k-combinations.
return factorial(n) / ( factorial(n - k) * factorial(k) )
def main():
global n_calls
# Run through a bunch of values for n and k.
max_n = 15
for n in range(1, max_n + 1):
# Worst case is when k is half of n.
worst_case = expected_n(n, n // 2)
for k in range(1, n + 1):
# Get the combos and count the calls.
n_calls = 0
vs = list(range(n))
cs = list(combos(vs, k))
# Our result agrees with:
# - itertools.combinations
# - the math
# - the worst-case analysis
assert cs == list(list(c) for c in combinations(vs, k))
assert len(cs) == expected_n(n, k)
assert n_calls <= worst_case
assert len(cs) <= worst_case
# Inspect the numbers for one value of n.
if n == max_n:
print [n, k, len(cs), n_calls]
main()
輸出：
[15, 1, 15, 1]
[15, 2, 105, 15]
[15, 3, 455, 105]
[15, 4, 1365, 455]
[15, 5, 3003, 1365]
[15, 6, 5005, 3003]
[15, 7, 6435, 5005]
[15, 8, 6435, 6435]
[15, 9, 5005, 6435]
[15, 10, 3003, 5005]
[15, 11, 1365, 3003]
[15, 12, 455, 1365]
[15, 13, 105, 455]
[15, 14, 15, 105]
[15, 15, 1, 15]
