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)
1 回答
牛魔王的故事
TA贡献1830条经验 获得超3个赞
Sayn是范围的大小，即要相加的数字量。将这些数字想象为二叉树的叶子，其中树中的每个节点代表一个子范围，当调用该函数对该节点的子范围求和时，它会进行两次递归调用，由该节点在二叉树中的两个子节点表示。
n有叶子的二叉树有2*n - 1节点，每个节点代表一次递归调用，因此递归函数被调用O(n)次。每次调用该函数时，它都会O(1)加上递归调用；因此完成的总工作是O(n)。
添加回答
举报
0/150
提交
取消