如何计算组合函数的复杂度？

Question

我正在尝试计算此函数的复杂性，同时考虑参数：'string' 的长度和组合字符串的长度 - 'size'。

我不知道 'size' 是否是计算复杂度的重要因素。

我或多或少知道这将是 len(string) 和 size 的组合的近似值：C(len(string), size)。

但是我如何计算它 'formally'，或者我如何表示它？ O(C(len(string), 大小))?

有人可以帮助我吗？非常感谢。

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', 2) 的输出是： ab 交流电广告 ae 公元前 bd 是光盘 ce 德

对于 comb('abcde', 3) 我们有：美国广播公司 abd 阿部酸性高手阿德 bcd 公元前 bde cde

Answer 1

首先，通过在每次迭代时创建额外的字符串切片来传递，您的函数会略有下降。如果您当前正在使用的字符串的长度为 m，则每次函数调用都会执行 O(m + (m-1) + (m-2) ... + 1) = O(m^2) 额外工作制作字符串切片，但您可以只传递索引以在它们之间进行迭代。您还可以在列表中收集给定组合的字符并在最后加入它们，因为使用不可变字符串类型一次构建一个 size 个字符的字符串是 O(size^2)当您可以在打印之前通过最后一个 O(size) 操作来加入生成的组合时，操作。所以我会做这些小的改变，这也有助于简化复杂性分析：

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) append 和 pop 进行回溯，以避免每次构建一个字符的组合的额外 size^2 时间复杂度。

让n代表字符串的长度，k=大小，你现在可以粗略地说这个算法运行在O(k*(n C k))时间，生成所有可能的 n 选择 k = n!/(n-k)!k!连击，然后用 O(k) 时间加入并打印每个连击。这大部分是正确的，但它确实忽略了递归构建每个组合所需的工作。如果您想比这更精确，则必须查看进行了多少次递归调用，以及每次递归调用中完成了多少工作。递归树可能是一种有用的思考方式：

我们最初的单个递归调用循环遍历整个字符串，执行常数时间 append/pop 工作并对 n 个可能的后缀（字符串 [1:]、字符串 [2:] 中的每一个进行递归调用。 ..字符串[n:])。这通常成立：每个递归调用所做的工作量与其接收的后缀 string[i:] 的长度成线性关系。每次递归调用所做的唯一非常量工作是对字符串的较小后缀生成进一步的递归调用，直到达到深度 k。

level: calls:        work/call:             total work:    
  1      1               n                  n = O(n C 1)

向下两个级别，有 n 个递归调用对字符串的后缀进行操作，（尽管一个对空后缀 string[n:] 进行操作并且它没有 work/generates 没有进一步的调用，所以有是我们关心的 n-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)

这些调用将生成 n-2 个大小为 1 的调用，n-3 个大小为 2 的调用... 1 个大小为 n-2 的调用。它变得有点混乱，此时通过归纳法更容易证明，但你可以将它降低 3 个级别，总工作量为 O(n C 3)，并且该模式适用于深度 k。本质上，每一层 i 负责生成所有大小为 i 的组合，并将这些组合向下传递到下一层以生成大小为 i+1 的组合。

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 C i) 的总和确实表示使用下面算法的检测版本中的断言进行的递归调用的次数）。可以使用不同类型的算法将我们打印所有组合的实际复杂度降低到最优 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))

如何计算组合函数的复杂度？

How do I compute the complexity of a combination function?

python

combinations

complexity-theory