为什么在分析递归算法的运行时间时会出现递归关系？

Question

为什么在分析递归算法的运行时间时出现递归关系？我听不懂，有人可以解释吗？

Answer 1

确实不是“引起”。递归关系描述递归算法解决方案每一步的行为，或多或少地降低了递归函数的复杂度，但不包括递归调用的开销。

例如，binary search进行比较，然后将输入数组分成两半，因此递归关系看起来像T(n) = T(n/2) + ϴ(1)，其中ϴ（1）（“ big-theta”）指的是固定时间操作，在这种情况下是比较。