分布式网络算法中轮复杂度的含义是什么？

Question

有人能解释一下分布式网络算法中时间复杂度的含义吗？DNA book by Panduranga中给出的定义如下：

在同步模型中，时间是由称为轮次的时钟节拍的数量来衡量的，也就是说，处理器以“锁定步长”进行计算。当运行分布式算法时，不同的节点可能需要不同的轮数才能完成。在这种情况下，所有节点所需的最大时间被认为是时间复杂度。

你能用一个简单的例子来解释上面的定义吗

Answer 1

假设你想要计算一个非常大的列表的和(比如说，10亿个数字)。为了加快速度，您使用了4个线程，每个线程计算2.5亿行的总和，然后可以将这些行相加得到总和。如果每个线程运行所需的时间为：

thread1 takes 43 seconds
thread2 takes 39 seconds
thread3 takes 40 seconds
thread4 takes 41 seconds

然后，您可以说此操作的运行时受耗时最长的线程的限制，在本例中为43秒。其他线程是否需要2秒都无关紧要，最长的任务决定了算法的运行时间。