python - 求和范围的时间复杂度

Question

我有以下函数，用于计算从 a 到 b 的所有数字的总和。我想知道如何找到它的时间复杂度(不使用主定理)。我希望得到直观的解释以及如何解决此类问题。

def sum_func(a, b):
    if a == b:
        return a

    mid = (a+b) // 2
    return sum_func(a, mid) + sum_func(mid+1, b)

Answer 1

假设n是范围的大小，即要相加的数字数量。将这些数字想象为 binary tree 的叶子，其中树中的每个节点代表一个子范围，当调用该函数对该节点的子范围求和时，它会进行两次递归调用，由该节点在二叉树中的两个子节点表示。

具有n个叶子的二叉树有2*n - 1个节点，每个节点代表一次递归调用，因此递归函数称为O(n) 次。每次调用该函数时，它都会执行 O(1) 工作加上递归调用；因此完成的总工作量为 O(n)。