百度面试题

只看该作者 · 2013-10-29 16:05

int func(unsigned int n)
{
if(n == 1)
      return 0;
if(n % 2 == 0)
      return 1 + func(n/2);
int x = func(n + 1);
int y = func(n - 1);
if(x > y)
      return y+1;
else
      return x+1;
}
这种的算法复杂度如何计算呢？

1万 · 2013-10-29 16:22

估计是log(N)

只看该作者 · 2013-10-29 16:33

算法导论有介绍哦,可以画出树状图,计算出来的, 不是一脑子就拍出来的.

只看该作者 · 2013-10-29 16:41

og(n)
下限很好证明，取n=2^k即可。
上限是log(n)要一些技巧。假设T是以上函数的复杂度，那么递推式是T(2k)=T(k)+1, T(2k+1)=T(k)+T(k+1)+3。
当k=2t的时候，T(2k+1)=2T(t)+T(t+1)+7。当k=2t+1的时候，T(2k+1)=T(t)+2T(t+1)+7。
令S(n)=max(T(1),...,T(n))。那么可以通过归纳法证明3S(t+1)+7 >= S(2k+1)。而对于偶数，3S(t+1)+7 >= S(2k)显然成立。这样的话S就满足一个下面的一个形式：S(n)<=3*S(ceil(n/4)) + 7。这样的话直接有S(n) = O(log(n)/log(3/4))=O(logn)。由于T(n)<=S(n)，T(n)=O(logn)

顺便log(n)/log(3/4)是一个S(n)的一个挺精确的估计。

只看该作者 · 2013-10-29 20:11

难度还是有的

只看该作者 · 2013-10-30 16:37

比较基础

只看该作者 · 2013-10-30 16:46

百度的待遇还是相当给力的

只看该作者 · 2013-10-30 16:55

百度还是很值得一去的

只看该作者 · 2013-10-30 17:04

今年百度招的人好像也不多

只看该作者 · 2013-10-30 18:52

很有水平的试题

只看该作者 · 2013-10-30 19:01

还有没有更多的百度面试题

只看该作者 · 2013-10-30 19:15

这个还是有难度的

1万 · 2013-10-30 19:28

如果是计算机专业该多好

百度面试题

相关下载

相关帖子