Spark/分布式算法的时间复杂度

Question

如果我们的时间复杂度低于

对于某些顺序算法，我们如何表达在 Spark（分布式版本）中实现的相同算法的时间复杂度。假设我们集群中有1个主节点和3个工作节点？

同样，我们如何表达O(n^2)Spark算法的时间复杂度？

此外，我们如何用复制因子 3 来表达 HDFS 中的空间复杂度？

提前致谢！！！！

Answer 1

忽略编排和通信时间（通常情况并非如此，例如，在对整个数据进行排序的情况下，操作不能只是“拆分”在不同的分区上）。

让我们做另一个方便的假设：数据完美地划分在 3 个分区中：每个节点都保存n/3数据。

这就是说，我认为我们可以将O(n^2)算法视为三个O((n/3) ^ 2)部分计算的总和（因此是最终的O((n/3) ^ 2)）。对于任何其他复杂性（O(n^2 log n) 将是O((n/3)^2 log(n/3))），这都是类似的。

至于hadoop中的复制因子，考虑到上述假设，由于操作将在副本之间并行执行（！=来自分区），因此复杂度将与单个“副本”的执行相同。