我为一个小型的自制计算机代数系统写了一个递归算法,在这个算法中,我对代数运算的操作数列表应用成对约化(仅相邻操作数,因为代数是非交换的)。我想知道我的算法的运行时复杂度(但不幸的是,作为一个物理学家,我已经经历了很长一段时间,因为我参加了任何处理复杂分析的下层CS课程)。在不详细讨论具体问题的情况下,我想我可以将算法形式化为一个函数f即“divide”步骤和一个函数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

在这种表示法中,函数fg接收列表作为参数和返回列表,输入/输出列表的长度是上述公式的参数和右侧。
对于整个故事,对应于fg的实际代码如下:
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

最佳答案

所以我想我现在明白了。要重述这个问题:当使用输入的size_get_binary_replacement调用_match_replace_binary时,查找对n的调用数。
定义函数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的最坏情况和最佳情况:
最佳情况(不减少):gg(n,m) = n + m
最坏情况(所有非中性还原):T_g(n, m) = 1g(n, m) = 1(我根据经验确定)
现在,master theorem (WP)适用于:
查看关于wp的说明:
T_g(n, m) = 2*(n+m) - 1(递归锚用于大小1)
我们在恒定时间内分裂成k=1个大小a = 2的子问题。
解决子问题后,合并结果所需的工作量n/2这是最坏情况下的d = 1(大约c = T_g(n/2, n/2)),最好的情况是1。
因此,在主定理WP页上的例子中,最坏情况的复杂性是n-1,并且最好的情况复杂度是n
实证试验似乎证明了这一结果。有人反对我的推理吗?

关于python - 嵌套递归函数的复杂度分析,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40535505/

10-14 18:35
查看更多