试题出自试卷《2021年下半年网络规划设计师考试上午真题（专业解析+参考答案）》

问题1选项
A.O(M ²)和O(N ²)
B.O(NM)和O(N ²)
C.O(N ²)和O(M ²)
D.O(NM)和O(M ²)

B

在链路状态路由算法中，每个路由器需要维护一个链路状态数据库（Link State Database，简称LSDB），其中存储着它所知道的所有其他路由器的链路状态信息。每当链路状态发生改变时，路由器都需要将这一信息向所有的连接路由器发送一份通告。对于每个路由器，需要与它相连的其他路由器发送一条链路状态通告消息，这一过程的复杂度为O(M)。因此，对于N个路由器而言，总的通告消息复杂度为O(NM)。
链路状态路由算法的执行时间复杂度为O(N²)。在算法的初始时刻，每个路由器只知道与它相连的链路信息，因此需要进行拓扑发现来获取整个网络的拓扑信息。在拓扑发现过程中，每个路由器通过向相邻路由器发送链路状态请求（Link State Request）消息来询问它所知道的其他路由器的链路状态信息。因此，在最坏情况下，每个路由器需要向网络中的所有其他路由器发送链路状态请求消息，这一过程的复杂度为O(N²)。
然后，在获取完整的网络拓扑信息之后，每个路由器需要计算出从自己到其他路由器的最短路径。具体来说，每个路由器需要对LFDB进行一次Dijkstra算法的执行，这一过程的复杂度为O(NlogN)。因此，对于N个路由器，总的计算时间复杂度为O(N²logN)。
综上所述，链路状态路由算法的链路状态通告消息复杂度为O(NM)，算法执行的时间复杂度为O(N²)。