每个人都知道 bubblesort 是 O(n^2)，但这是基于排序所需的比较次数。我有一个问题，如果我不关心比较次数，只关心输出时间，那么你如何分析这个？有没有办法对输出时间进行分析而不是比较？
例如，如果您可以进行冒泡排序并对所有对进行并行比较(即使是奇数比较)，那么吞吐量时间将类似于 2n-1 吞吐量时间。比较的次数会很高，但我不在乎，因为最终吞吐时间很快。
那么本质上，对于总体并行性能时间有没有共同的分析呢？如果是这样，请给我一些关键术语，其余的我会从谷歌中学习。
最佳答案
并行编程在这里有点转移注意力。 仅根据大 O 符号对运行时做出假设可能会产生误导。要比较算法的运行时间，您需要完整的方程式，而不仅仅是大 O 表示法。
问题是大 O 表示法告诉您主导项为 n去无穷大。但是运行时间在 n 的有限范围内.这从连续数学(我的背景)中很容易理解。
考虑 y=Ax和 y=Bx^2大 O 符号会告诉你 y=Bx^2比较慢。但是，在 (0,A/B) 之间它小于 y=Ax .在这种情况下，对于 x<A/B，使用 O(x^2) 算法可能比使用 O(x) 算法更快。 .
事实上，我听说过排序算法从 O(nlogn) 算法开始，然后在 n 足够小时切换到 O(n^2) 对数。
最好的例子是矩阵乘法。天真的算法是 O(n^3)，但有些算法可以将其降低到 O(n^2.3727)。然而，我见过的每个算法都有一个如此大的常数，以至于朴素的 O(n^3) 仍然是 n 的所有粒子值最快的算法。而且这看起来不会很快改变。
所以您真正需要的是要比较的完整方程式。类似于 An^3 (让我们忽略低阶项)和 Bn^2.3727 .在这种情况下，B 非常大，以至于 O(n^3) 方法总是获胜。
并行编程通常只是降低常量。例如，当我使用四个内核进行矩阵乘法时，我的时间从 An^3 开始。至 A/4 n^3 .并行冒泡排序也会发生同样的事情。你会减少常量。所以有可能对于 n 的某些值范围您的并行冒泡排序将击败非并行(甚至可能是并行)合并排序。不过，与矩阵乘法不同，我认为范围会非常小。
关于algorithm - 并行算法分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21001939/