如何计算组合函数的复杂性？ [英] How do I compute the complexity of a combination function?

问题描述

我正在尝试计算此函数的复杂性，同时考虑以下参数：‘字符串’的长度和组合字符串的长度-‘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’，2)的输出为： AB 交流 广告 声发射 卑诗省 BD BE CD 行政长官 De

对于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)

向下两层，有n个递归调用对字符串的后缀进行操作(尽管有一个对空的后缀、字符串[n：]进行操作，并且它不工作/不生成进一步的调用，所以我们关心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 C3)，这个模式一直保持到深度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 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))

这篇关于如何计算组合函数的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！