algorithm - 分布式算法的空间复杂度

Question

网上有很多关于不同算法的空间复杂度计算的回答问题。所有算法本质上都是集中的。我们如何计算半集中式和分布式算法的空间复杂度？分布式算法在多个服务器上运行。每个服务器的空间复杂度是否应该单独计算？

-谢谢

标签： algorithmspace-complexitydistributed-algorithm

Answer 1

服务器的数量是有限的，因此理想情况下不应影响渐近符号的复杂度计算。如果您仍想显示随着服务器数量达到较高值时的内存消耗量，您将需要在每台服务器上使用服务器数量来计算多个内存复杂度。