注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简单代码

寻找代码的灵魂

 
 
 

日志

 
 
关于我

对于本博客内所有原创文章和代码的引用必须标明“来源:http://simplesource.blog.163.com/”。如需应用于商业目的必须经本人同意,本人对所有原创文章和代码保留一切权利。 PS:需要部分程序源代码的请留下邮箱地址

网易考拉推荐

一道google笔试题以及解答  

2007-05-13 08:37:59|  分类: 技术文献 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 一道google笔试题以及解答

我的一个好朋友参加了一次google招聘的笔试,遇到一道算法题不会做。我思考了一下,初步给出了以下解答,可能有纰漏和错误,仅供大家参考,高手也可以给出自己的算法进行解答,看看哪种算法最优。

问题:写一个算法,求一个有n个节点的二叉树中有m个节点的连通图的个数,分析算法复杂度。

 

解决方法(分治法)

1、将每个节点以及这个节点的所有子节点看作是一棵子树

 

2、设每棵子树有一组属性:n, N[n + 1] M[n + 1]

n:  组大小

N[0~n]: 含有树根节点的连通图个数(N[i]表示节点数为i的连通图个数)

M[0~n]: 不含树根节点的连通图个数(M[i]表示节点数为i的连通图个数)

注意:N和M数组下标为0~n,大小为n + 1

(实际上组的大小必定为这棵树的子节点数目 + 1)

 

3、从叶子节点开始遍历

  举例说明:

a)       对于一棵没有子节点的树:n = 1,N[0] = 0, N[1] = 1, M[0] = 0, M[1] = 0

b)      对于一棵只有一边子树的树:

 

因为B的属性已经求得,假设为:

nB

N[0, NB1, NB2…NBn]

M[0, MB1, MB2…MBn]

则A的属性为:

nB + 1

N[0, 1, NB1 , NB2 , …, NBn ]

M[0, NB1 + MB1, NB2 + MB2, …, NBn + MBn, 0]

c)       对于一棵有两边子树的树:

 

因为B, C的属性已经求得,假设为:

B

nB

N[0, NB1, NB2…NBn]

M[0, [MB1, MB2…MBn]

C

nC

N[0, NC1, NC2…NCn]

M[0, MC1, MC2…MCn]

则A的属性为:

n = nB + nC + 1

N[i] 的计算:

N[] = [0](清零)

N[1] = 1

for(j = 0; j <= nB; j++)

{

for(k = 0; k <= nC; k++)

{

       N[ j + k + 1] += NBj + NCk;

}

}

 

M[0, NB1 + MB1 + NC1 + MC1, NB2 + MB2 + NC2 + MC2, …, NBn + MBn + NCn - 1 + MCn - 1, 0]

4、最后求出根节点的属性后

取N[m] + M[m]即所求连通图的个数

 

算法复杂度分析:

整个算法中最复杂的是第三步中的两重循环,如果二叉树为完全二叉树T(n)(n表示节点数),则  T(1)               需要计算0次

     T(3)               需要计算(1 + 1) * (1 + 1) = 4次

     T(7)               需要计算(1 + 1) * (1 + 1) * 2 + (3 + 1) * (3 + 1) = 24次

     T(15)             需要计算(1 + 1) * (1 + 1) * 2^2 + (3 + 1) * (3 + 1) * 2^1 + (7 + 1) * (7 + 1) * 2^0 = 112次

     T(2^n – 1)      需要计算T(2^(n – 1) - 1) * 2 + (2^(n - 1)) * (2^(n - 1)) 次

                     = (1 + 1) * (1 + 1) * 2^(n - 2) + (3 + 1) * (3 + 1) * 2^(n - 3) + (7 + 1) * (7 + 1) * 2^(n - 4) +… + (2^(n - 1)) * (2^(n - 1)) * (2^0) = 2^n * (2^(n - 1) - 1) = (2^n - 1 + 1) * (2^n - 1 - 1) = (N + 1) *(N - 1)/ 2 = (N * N - 1) / 2

即对于一棵节点数为N的完全二叉树需要计算约N*N/2次

所以算法复杂度为O(n^2)

  评论这张
 
阅读(1091)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018