algorithm - 为数字供电作为分而治之的解决方案

Question

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

Answer 1

在每一步中，问题都被分成两个相同的小部分。由于它们是相同的，因此无需对每一个进行计算。因此不需要乘数 2。