【题干描述】:
我们共有n台服务器,每台服务器可以和若干个子服务器传输数据,n台服务器组成一个树状结构。
现在要将一份数据从root节点开始分发给所有服务器。
一次数据传输需要一个小时时间,
一个节点可以同时对k个儿子节点进行并行传输,
不同节点可以并行分发。
问,全部分发完成,最短需要多少小时?
【示例】:
当共有5台服务器,其树状结构为
0
/ \
1 2
/ \
3 4
假设每一台服务器同时可以对1个儿子节点(k=1)并行传输,最优的数据传输过程示例如下:
第一个小时,0 -> 1;
第二个小时,1->3 & 0->2;
第三个小时,1 -> 4;
所以当k=1时,全部分发完成最短需要3个小时。
假设每一台服务器同时可以对2个儿子节点(k=2)并行传输,最优的数据传输过程示例如下:
第一个小时,0 -> 1 & 0 -> 2;
第二个小时,1 -> 3 & 1 -> 4;
所以当k=2时,全部分发完成最短需要2个小时。