算法分析与设计第二次作业
姓名:赵翔宇 学号:SA14011047
第二部分 分布式算法
EX 2.1
问题:
分析在同步和异步模型下,convergecast算法的时间复杂性。
答:
(1) 同步模型中:最坏情况下,算法执行的每一轮中只有一个msg传递,而此时生成树汇聚
最大值的算法最多执行n-1轮,也就是说同步情况下的时间复杂度为O(n-1)。
(2) 异步模型中:在异步模型的汇集算法的每个容许执行中,树中每个距离pr为t的处理器
至多在时刻t接收消息M,因此对于每个节点而言,它到它所有子节点中t最大的路径决
定了它本身时间花费。因此在最坏情况下,仍应该是同步模型下的最坏情况,即生成树
中除了末端节点每一个节点只有一个子节点,此时时间复杂度仍为O(n-1)。
EX 2.2
问题:
证明在引理2.6中,一个处理器在图G中是从P
r
可达的,当且仅当它的parent变量曾被赋过值。
答:
证明:
:因为图G是由parent和children确定的静态图,任一节点在收到M后才会加入到图中。即
可达节点收到过M,执行了算法2.2的第五行。由于是容许执行的,所以第7行(parent:=j)也
会执行。
:若算法2.2的第7行执行过了,因为是容许执行,则必然有第5行也执行过了。即节点收
到过M。而M又是从pr发出的,所以该节点是从pr可达的。
评论0