p*****e
发帖数: 537 | 1 两个recursive的function,主要的关系是：
f(x) = f(x-1) + g(x)
g(x) = f(x-1) + g(x/2)
边界条件大概就是f(1) = a, g(0) = b什么的，不过也不重要.
最后要求f（x）的time complexity。
这个题怎么做啊？ |
p*****e
发帖数: 537 | |
l*****a
发帖数: 14598 | 3 考这个的地方就不要去了
【在 p*****e 的大作中提到】
: 两个recursive的function,主要的关系是：
: f(x) = f(x-1) + g(x)
: g(x) = f(x-1) + g(x/2)
: 边界条件大概就是f(1) = a, g(0) = b什么的，不过也不重要.
: 最后要求f（x）的time complexity。
: 这个题怎么做啊？
|
p*****e
发帖数: 537 | 4 这是个online quiz，不是interview的题。interview问这个就太没天理了。
【在 l*****a 的大作中提到】
: 考这个的地方就不要去了
|
w*****d
发帖数: 105 | 5 我觉得是logN吧：
f(n)=f(n-1)+g(n)=f(n-1)+f(n-1)+g(n/2)
=2f(n-1)+g(n/2)
=2f(n-1)+f(n/2)+g(n/4)
=...
g(x)按照logN速度递减。
|
c******e
发帖数: 73 | 6 f(n)=f(n-1)+g(n)=f(n-1)+f(n-1)+g(n/2)
=2f(n-1)+g(n/2)
=2f(n-1)+f(n/2)+g(n/4)
= 4f(n-2) +....
= 8f(n-3) + .....
= 2^n (f(1) + .....
should not it be exponential? |
s**x
发帖数: 7506 | |
