algorithm - 描述分、治、组合分而治之算法的各个部分

Question

我正在解决练习测验并遇到以下问题

写下与以下分治算法相对应的递归，准确地标记每个组件：划分、征服和组合。

1. Foo (p, r):
2.     if p = r
3.          return (1)
4.     else
5.         s ← 1
6.         for i = p to r
7.             s ← s * i
8.         q ← Foo(p, r − 1) * s
9.     return (q)

---

我试图回答。

1. 让 T(n) 是 Foo 在 p 到 r 上所做的工作，所以 T(n) 等价于 Foo(p, r)，其中 n 是 r - p + 1。

2. 我得到以下递归 T(n) = T(n - 1) + Θ(n) + Θ(1)

3. 除法部分将是一个常数 Θ(1)，它对应于 r-1 操作。

4. 征服部分将是递归解决子问题的 T(n - 1)。

5. 组合部分是 T(n - 1) * s 的乘法运算的常数 Θ(1)。

---

但这似乎是错误的，因为我没有提到 Θ(n)。第 6,7 行的 Θ(n) 应该属于划分、征服、组合的哪一部分？

Answer 1

s accumulates from p to r so this would seem to fall into the "combining" part. So we have Θ(n) coming from combining.

As we combine the elements back together, we essentially have to zip the back up over the n elements.