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

Question

我已经为一个小型的本土计算机代数系统编写了一个递归算法，其中我将成对归约应用于代数运算的操作数列表（仅相邻操作数，因为代数是非交换的） .我试图了解我的算法的运行时复杂性（但不幸的是，作为一名物理学家，我已经有很长时间没有参加任何处理复杂性分析的本科 CS 课程）。在不深入具体问题的细节的情况下，我认为我可以根据作为 "divide" 步骤的函数 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 接收列表作为参数和 return 列表，length input/output 列出了上面等式的参数和右边。

完整的故事，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

的大小

Answer 1

所以我想我现在明白了。重述问题：求出调用 _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
最坏情况（所有非中性还原）：g(n, m) = 1，T_g(n, m) = 2*(n+m) - 1（我根据经验确定）

现在，master theorem (WP) 适用：

查看 WP 上的描述：

k=1（递归锚点用于大小 1）
我们在常数 (d = 1) 时间

a = 2

n/2

解决子问题后，合并结果所需的工作量为c = T_g(n/2, n/2)。这在最坏的情况下是 n-1（大约 n），在最好的情况下是 1

因此，按照主定理 WP 页面上的示例，最坏情况复杂度为 n * log(n)，最佳情况复杂度为 n

实证试验似乎证实了这一结果。对我的推理有异议吗？

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

Complexity analysis of nested recursive functions

python

algorithm

recursion

complexity-theory