直方图并行实现的工作复杂度

Question

我已经成功地制定了在基于 CUDA 的环境中使用的直方图的实现。 我难以理解的是算法的工作复杂度。

我可以说串行实现的复杂度是线性的 - O(n) 其中 n = 输入的数量基于我们必须至少循环所有输入一次的事实。

实施将：

• 将测量结果分组

• 将每组测量值传递给单独的线程

• 在每个线程中计算局部直方图

• 将它们缩小为全局直方图

我是否必须计算出每个步骤的复杂性并合并？

Answer 1

您应该计算每一步的复杂度并取最大的。在你的情况下，所有步骤都是线性的，因此整个算法的复杂度是线性的。