求和范围的时间复杂度

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

Sayn是范围的大小，即要相加的数字量。将这些数字想象为二叉树的叶子，其中树中的每个节点代表一个子范围，当调用该函数对该节点的子范围求和时，它会进行两次递归调用，由该节点在二叉树中的两个子节点表示。n有叶子的二叉树有2*n - 1节点，每个节点代表一次递归调用，因此递归函数被调用O(n)次。每次调用该函数时，它都会O(1)加上递归调用；因此完成的总工作是O(n)。