2
我解决一个练习测验分而治之算法的部分和整个以下问题描述的鸿沟,征服,结合
写下对应下面鸿沟复发而治之算法来,精确地标记每个组成部分:划分,征服和组合。
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)
我的上述问题的回答。
令t(n)是由富在p完成至r的工作,所以T(n)是等效的Foo(P,R)的,其中n为r - P + 1
- (1)
我得到下面的复发T(n)= T(n-1)+Θ(n)+Θ(1)分割部分将是对应于r-1的常数Θ操作。
征服部分将是递归解决子问题的T(n-1)。
组合部分是用于T(n-1)* s的乘法运算的常数Θ(1)。
但似乎错了,因为我并没有提到Θ(N)。线6,7的Θ(n)落入什么区分,征服,结合的哪一部分?
嗯,“Theta”来自上面的代码?或“T”? –
@JimClay我的意思是渐近符号的theta,并编辑我的帖子,试图澄清我的意思是T(n) – ayh
哇,现在甚至除以1(自称只有一次)可以称为“分而治之”。 .. – kennytm