问题描述
我正在尝试计算此函数的复杂性，同时考虑以下参数：‘字符串’的长度和组合字符串的长度-‘SIZE’。
我不知道"大小"是否是计算复杂性的重要因素。
我或多或少知道它将是len(字符串)和大小的组合的近似值：C(len(字符串)，大小)。 但我如何才能计算出它的形式，或者我如何表示它呢？O(C(len(字符串)，大小))？
有人能帮帮我吗？非常感谢。
def comb(string, size, r=''):
if len(r) == size:
print(r)
return
for i, e in enumerate(string):
comb(string[i + 1:], size, r + e)
comb('abcde', 2)
comb('abcde', 3)
对于comb(‘abcde’，3)，我们有： ABC 阿布德 安倍 ACD 王牌 阿德 BCD BCE BDE CDE
推荐答案
首先，通过在每次迭代时向下传递额外的字符串片，您的函数会受到轻微的压力。如果当前处理的字符串的长度为m，则执行O(m+(m-1)+(m-2)...+1)=O(m^2)=O(m^2)每个函数调用以生成字符串片，但您可能只是向下传递索引以在其间进行迭代。您还可以收集列表中给定组合的字符并在最后连接它们，因为使用不变的字符串类型每次构建一个包含size个字符的字符串是一个O(大小^2)操作，而您可以在打印之前完成最后一个O(大小)操作来连接生成的组合。因此，我将做这些小改动，这将有助于使复杂性分析变得更简单：
def combos(string, size):
def _combos(i = 0, partial = []):
if len(partial) == size:
print(''.join(partial))
return
for j in range(i, len(string)):
partial.append(string[j])
_combos(j+1, partial)
partial.pop()
_combos()
combos('abcde', 2)
combos('abcde', 3)
我向下传递一个索引i以迭代原始字符串，而不是为每个调用构建一个新字符串，并且我将r重构到列表partial，我直接对该列表进行变异，并在以len==Size连接之前使用O(1)追加和弹出来避免每个组合额外的大小^2时间复杂性，每次构建该组合一个字符。
n代表字符串的长度，k=SIZE，现在可以粗略地说，该算法运行O(k*(N C K))时间，生成所有可能的n选择k=n！/(n-k)！k！组合，然后花费O(K)时间加入并打印每个组合。这在很大程度上是正确的，但它确实忽略了递归构建每个组合所需的工作。如果您想要比这更精确，您必须查看进行了多少递归调用，以及在每个递归调用中执行了多少工作。考虑这一点，递归树可能是一个有用的方法：
我们最初的单次递归调用循环遍历整个字符串，执行恒定时间的追加/弹出工作，并对n个可能的后缀(字符串[1：]、字符串[2：]...字符串[n：])进行递归调用。一般来说，这一点是成立的：每个递归调用的工作量与它接收的后缀字符串[i：]的长度成线性关系。每个递归调用所做的唯一非常量工作是在字符串的较小后缀上生成进一步的递归调用，直到达到深度k。
level: calls: work/call: total work:
1 1 n n = O(n C 1)
level: calls: work/call: total work:
2 n varies from 0 to n-1 1 + 2... + n-1 = n(n-1)/2 = O(n C 2)
level: calls: work/call: total work:
3 n(n-1)/2 varies from 0 to n-2 n(n-1)(n-2)/(2*3) = O(n C 3)
...
k n(n-1)..(n-k+1)/(k*(k-1)...(2) O(k) k*calls = k*n!/((n-k)!*k!) = O (k*(n C k))
这可能比最初估计的O(k*(N C K))更糟糕，因为我们正在做一些不必要的工作来构建部分组合，其中一些实际上并没有使用。(您可以验证从i=0到k的组合的总和(N Ci)确实表示在以下算法的插装版本中使用断言进行的递归调用的数量)。使用不同的算法可以将打印所有组合的实际复杂度降低到最优O(k*(N C K))，但该算法并不是最优的，而格雷码则是一个完全不同的主题。
from functools import cache
@cache
def fact(n):
if n <= 1: return 1
return n * fact(n-1)
# n choose k: n!/(k!(n-k)!)
def nCk(n, k): return fact(n) / (fact(n-k) * fact(k))
# sum of nCk(n, i) from i = 0 to k (expected number of recursive calls)
def expect(n, k):
expectedCalls = 0
for i in range(0, k+1):
expectedCalls += nCk(n, i)
return expectedCalls
def combos(string, size):
callCount = 0
result = []
def _combos(i = 0, partial = []):
#print(f"_combos({i}, {partial})")
nonlocal callCount
callCount += 1
if len(partial) == size:
result.append(''.join(partial))
return
for j in range(i, len(string)):
partial.append(string[j])
_combos(j+1, partial)
partial.pop()
_combos()
print(f'numCombos({string}, {size}):', len(result))
print('callCount:', callCount)
assert(callCount == expect(len(string), size))
return result
print(combos('abcde', 2))
print(combos('abcde', 3))
print(combos('abcde', 5))
这篇关于如何计算组合函数的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！