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) .