求和范围的时间复杂度
Time complexity of summing ranges
我有以下函数计算从 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)
说 n 是范围的大小，即要加在一起的数字的数量。将这些数字想象成 binary tree 的叶子，其中树中的每个节点代表一个子范围，当调用该函数对该节点的子范围求和时，它会进行两次递归调用，该调用由二进制中该节点的两个子节点表示树.
一个有n个叶子的二叉树有2*n - 1个节点，每个节点代表一次递归调用，所以递归函数被调用了O(n)次。每次调用该函数时，它都会 O(1) 加上递归调用；因此完成的总工作量是 O(n).
我有以下函数计算从 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)
说 n 是范围的大小，即要加在一起的数字的数量。将这些数字想象成 binary tree 的叶子，其中树中的每个节点代表一个子范围，当调用该函数对该节点的子范围求和时，它会进行两次递归调用，该调用由二进制中该节点的两个子节点表示树.
一个有n个叶子的二叉树有2*n - 1个节点，每个节点代表一次递归调用，所以递归函数被调用了O(n)次。每次调用该函数时，它都会 O(1) 加上递归调用；因此完成的总工作量是 O(n).