大数据平台的时间复杂度表示法

Question

我正在重新设计Hadoop/MapReduce框架的一些经典算法。我想知道是否有任何既定的方法来表示大(O)类表达式来衡量时间复杂性？

例如，假设n(=10亿)数的简单平均计算是O(n) +C操作，使用simple For循环，或者O(log)，为了简单起见，我假设除法是一个常数时间运算。如果我打破了MapReduce的大规模并行算法，通过将数据除以k个节点，我的时间复杂度就会简单地变成O(n/k) +C+ C‘。在这里，C‘可以假定为作业计划时间开销。请注意，没有涉及洗牌，还原机的工作几乎是微不足道的。

我感兴趣的是一个更完整的分析算法与迭代循环的数据，并涉及沉重的洗牌和还原操作。如果可能的话，我想包括I/O操作和数据的网络传输。

Answer 1

大O时间复杂度设计用于分析抽象算法，不依赖于实现。

如果您对实际实现的系统的性能感兴趣，包括洗牌、I/O操作和网络传输，那么查看基准测试/分析就会更有用。基准测试/分析通过查找特定操作的观察时间来发现经验性能。