这种递归算法的复杂性是什么？

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

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

哪里C有些不变.我们可以通过反复替换和发现模式来解决这种关系:

总和的上限是m多少？当发生停止条件len(a)是奇数.这可能是任何地方之间N和1,取决于素数分解的N.在更糟糕的情况下,N是2的幂,所以函数递归直到len(a) = 1,即