基于轮的分布式算法的开销

Question

我有一个基于轮的分布式算法，适用于n个节点上的网络。

我知道一轮的成本(就资源使用而言)是O(n)。但是，我不知道轮数，基本上它们可以重复到时间的尽头(无穷大)。

那么这个算法的成本是多少呢？我们能说它是O(n)吗？

Answer 1

你不清楚你试图评估的大O是什么。如果你的意思是“以循环方式将n个任务分配给一个大小为n的集群”，那么这将是O(n)。如果你的意思是“以循环方式分配下一个任务”，那么你只需要找到下一个节点，这可以在O(1)中完成。

如果您有一些其他算法，您打算使用循环分布作为其中的一部分，则不能仅通过查看这一部分来确定该算法的大O。