问个算time complexity的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个算time complexity的问题

问个算time complexity的问题# JobHunting - 待字闺中

r*x2014-03-19 07:03

1 楼

LD前一段日子回国，目前希望8月份之前能来美国，她是F2，我现在处于opt，在一家公
司上班。我找不到类似的经历，请问大家，我应该准备些啥材料。有类似经历能够分享
的同学吗？谢谢！

p*e2014-03-19 07:03

2 楼

两个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。
这个题怎么做啊？

J*o2014-03-19 07:03

3 楼

我也有类似的问题，
麻烦有类似经历的前辈出来讲一下。

【在 r*****x 的大作中提到】

: LD前一段日子回国，目前希望8月份之前能来美国，她是F2，我现在处于opt，在一家公
: 司上班。我找不到类似的经历，请问大家，我应该准备些啥材料。有类似经历能够分享
: 的同学吗？谢谢！

p*e2014-03-19 07:03

4 楼

这个f（x)是linear的，对不？

l*a2014-03-19 07:03

5 楼

考这个的地方就不要去了

【在 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*e2014-03-19 07:03

6 楼

这是个online quiz，不是interview的题。interview问这个就太没天理了。

【在 l*****a 的大作中提到】

: 考这个的地方就不要去了

w*d2014-03-19 07:03

7 楼

我觉得是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*e2014-03-19 07:03

8 楼

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?