当我们在理论计算机科学中用分而治之的算法编写一个数的幂时，在我看来，运行时是T(n) = 2T(n/2) + Θ(1)，但根据我老师的幻灯片，它是T(n) = T(n/2) + Θ(1)。为什么？我加了2是因为算法被分成了2个子问题？我错了吗？
最佳答案
在每个步骤中，问题被分成两个相同的小部分因为它们是相同的，所以不需要对每一个进行计算。因此，不需要乘法器2。
当我们在理论计算机科学中用分而治之的算法编写一个数的幂时，在我看来，运行时是T(n) = 2T(n/2) + Θ(1)，但根据我老师的幻灯片，它是T(n) = T(n/2) + Θ(1)。为什么？我加了2是因为算法被分成了2个子问题？我错了吗？
最佳答案
在每个步骤中，问题被分成两个相同的小部分因为它们是相同的，所以不需要对每一个进行计算。因此，不需要乘法器2。