一道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)
Posts
No comments:
Post a Comment