python - 这个递归算法的复杂度是多少？

Question

下面算法的复杂度是否为O(nlogn)？

让我感到困惑的是，这个算法除法两次，而不是像常规的 O(nlogn) 算法那样除一次，而且每次它的工作时间都为 O(n)。

def equivalent(a, b):

    if isEqual(a, b):
        return True

    half = int(len(a) / 2)
    if 2*half != len(a):
        return False

    if (equivalent(a[:half], b[:half]) and equivalent(a[half:], b[half:])):
        return True

    if (equivalent(a[:half], b[half:]) and equivalent(a[half:], b[:half])):
        return True

    return False

Answer 1

对 equivalent 的 4 次递归调用中的每一次都将输入数据量减少了 2 倍。因此，假设 a 和 b 具有相同的长度，并且isEqual 具有线性时间复杂度，我们可以构造整体复杂度的递归关系:

C 是一些常量。我们可以通过重复替换和发现一个模式来解决这个关系:

求和的上限是多少，m？当len(a) 为奇数 时，会出现停止条件。这可能介于 N 和 1 之间，具体取决于 N 的质数分解。在最坏的情况下，N 是 2 的幂，因此函数递归直到 len(a) = 1，即