t*****e
发帖数: 53 | 1 T(n) = 3 * T(n/6) + T(n/2) + 2
T(1) = 1;
How to solve T(n)? |
J******d
发帖数: 506 | 2 T(n)=5/3*n-2/3
not sure if it is unique tho. |
f***e
发帖数: 43 | 3 Good guess, T(n) is a linear function of n, actually it is unique,
solve it for continuous case,
t(x)=3t(x/6)+t(x/2)+2
take derivative
t'(x)=1/2 t'(x/6) + 1/2 t'(x/2)
Expand t(x) using polynomial, only the linear term remains, |
s*y
发帖数: 124 | 4 what about functions that are not polynomial?
【在 f***e 的大作中提到】
: Good guess, T(n) is a linear function of n, actually it is unique,
: solve it for continuous case,
: t(x)=3t(x/6)+t(x/2)+2
: take derivative
: t'(x)=1/2 t'(x/6) + 1/2 t'(x/2)
: Expand t(x) using polynomial, only the linear term remains,
|
J******d
发帖数: 506 | 5 Actually, as long as the function is continuous, you can prove the
solution is what posted above and it is unique. We don't even need to
assume it is differentiable.
【在 s*y 的大作中提到】
: what about functions that are not polynomial?
|
t*****e
发帖数: 53 | 6 JunkFood,
Can you explain how you get your solution?
Thanks. |
J******d
发帖数: 506 | 7 抱歉，刚才仔细看了一下发现我的做法不但要求T(x)连续，并且还要求T(x)在x=0可导:
令F(x) = (T(x)+2/3)/x
根据题目，我们有
F(x) = (F(x/6)+F(x/2))/2
假设T(x)连续并在x=0可导，则F(x)连续。
对于任意K, F(x)在[0,K]必定取到最大值。假设最大值在x_0取得。那么因为
F(x_0)是F(x_0/6)和F(x_0/2)的平均值，我们必然有F(x_0)=F(x_0/6)=F(x_0/2).
那么对x_0/6使用上面同样的推理我们有,
F(x_0)=F(x_0/6)=F(x_0/36)=...=F(0)
因此，F(x)在x=0取得最大值。
同理F(x)在x=0取得最小值。因此F(x)必为常数。根据T(1)=1知F(x)=5/3，因此，
T(x)=5/3*x-2/3.
【在 t*****e 的大作中提到】
: JunkFood,
: Can you explain how you get your solution?
: Thanks.
|
p*****k
发帖数: 318 | 8 this is just a shot in the dark:
would guess the question is from some d&c algorithm - one is
more interested in the asymptotic behavior of T when n->infty.
(T is probably only defined on N->N, so n/6 could be floor[n/6], etc)
then one needs the general version of the master theorem:
http://en.wikipedia.org/wiki/Akra-Bazzi_method |
