嵌套递归函数的复杂性分析

我已经写出了一个小本地计算机代数系统的递归算法，其中我将代数运算的操作数列表中的成对还原应用于相邻操作数列表，因为代数是非交换）。我想了解我的算法的运行时复杂性（但不幸的是，作为一名物理学家，自从我选修了处理复杂性分析的本科CS课程以来，这已经很长时间了）。在没有详细讨论具体问题的情况下，我想我可以用一个功能f来形式化算法，这是一个“分裂”步骤，而函数g组合了结果。然后我的算法将采取以下形式表示：嵌套递归函数的复杂性分析

f(1) = 1 # recursion anchor for f 
f(n) = g(f(n/2), f(n/2)) 

g(n, 0) = n, g(0, m) = m   # recursion ... 
g(1, 0) = g(0, 1) = 1    # ... anchors for g 

     /g(g(n-1, 1), m-1) if reduction is "non-neutral" 
g(n, m) = | g(n-1, m-1)  if reduction is "neutral" 
      \ n + m    if no reduction is possible

在此标记，功能f和g接受列表作为参数，并返回列表，与长度的输入/输出列出的作为论据和上面方程的右边。

完整故事，对应于f和g实际的代码如下：

def _match_replace_binary(cls, ops: list) -> list: 
    """Reduce list of `ops`""" 
    n = len(ops) 
    if n <= 1: 
     return ops 
    ops_left = ops[:n//2] 
    ops_right = ops[n//2:] 
    return _match_replace_binary_combine(
      cls, 
      _match_replace_binary(cls, ops_left), 
      _match_replace_binary(cls, ops_right)) 


def _match_replace_binary_combine(cls, a: list, b: list) -> list: 
    """combine two fully reduced lists a, b""" 
    if len(a) == 0 or len(b) == 0: 
     return a + b 
    if len(a) == 1 and len(b) == 1: 
     return a + b 
    r = _get_binary_replacement(a[-1], b[0], cls._binary_rules) 
    if r is None: 
     return a + b 
    if r == cls.neutral_element: 
     return _match_replace_binary_combine(cls, a[:-1], b[1:]) 
    r = [r, ] 
    return _match_replace_binary_combine(
      cls, 
      _match_replace_binary_combine(cls, a[:-1], r), 
      b[1:])

我感兴趣的时候最坏情况数get_binary_replacement是呼吁，根据大小ops

来源

2016-11-10 Michael Goerz

您是否尝试应用_Master Theorem_？ https://en.m.wikipedia.org/wiki/Master-Theorem – clemens

我知道必须有一个关于此的定理！乍一看，它似乎完全适用于我的情况，我会通读详细信息，并了解我的位置 –

@macmoonshine我不认为主定理可以直接应用。它处理'T（n）= aT（n/b）+ f（n）'类型的递归，但OP问题的类型为T（n）= g（T（n/b））， T（n/c））+ f（n）'，我看不出一种简单的方法将其减少到第一种形式......无论如何，首先要做的就是获得'g'的复杂性，因为它不依赖于'f'。之后，你只需用'f（n/2）'替换这个复杂性的两个参数，然后你可以以主定理的形式结束，假设它仍然是线性的... – Bakuriu

所以我想我现在已经明白了。要重新解决问题：拨打_match_replace_binary并输入大小为n的输入时，找到拨打_get_binary_replacement的电话号码。

定义函数g(n, m)（如在原来的问题），其中的_match_replace_binary_combine的两个输入的大小映射到输出
的大小定义一个函数T_g(n, m)那的_match_replace_binary_combine两个输入的大小映射到获得结果所需的拨打g的总次数。这也是（最坏情况）呼叫数量来_get_binary_replacement为每次调用_match_replace_binary_combine电话_get_binary_replacement最多一次

我们现在可以考虑为g最坏的情况下，最好的情况：

最好的情况下（无还原）：g(n,m) = n + m，T_g(n, m) = 1
最坏情况（所有非正eutral还原）：g(n, m) = 1，T_g(n, m) = 2*(n+m) - 1（I凭经验确定此）

现在，master theorem (WP)适用：

通过上WP的描述状况：

k=1（递归的锚为大小1）
我们分成a = 2大小为n/2的子问题常量（d = 1）t ime
解决子问题后，合并结果所需的工作量为c = T_g(n/2, n/2)。这是最好的情况下，在最坏的情况下n-1（大约n）和1

因此，以下对主定理的WP页上的实施例中，最坏情况下的复杂性是n * log(n)，而最好的情况下，复杂度是n

经验性试验似乎证实了这一结果。任何反对我的推理？

来源

2016-11-11 19:03:49

嵌套递归函数的复杂性分析

回答

相关问题