为一个数字提供分而治之的解决方案

Question

当我们在理论计算机科学中将一个数字作为一个分而治之的算法写作时，运行时在我看来会是T(n) = 2T(n/2) + Θ(1)，但根据我老师的幻灯片，它是T(n) = T(n/2) + Θ(1)。为什么？我添加了2，因为算法分解成2个子问题？我错了吗？

Answer 1

在每个步骤中，问题分为两个小的相同部分。由于这些都是相同的，所以不需要为每一个进行计算。因此不需要乘数2。