大家都知道bubblesort是O(n^2)，但是这是基于对此进行排序所需的比较次数。我有一个问题，如果我不关心比较次数，而是输出时间，那么你如何分析这个？有没有办法对输出时间进行分析而不是比较？例如，如果您可以对所有对进行冒泡排序并进行并行比较（即使是奇数比较），那么吞吐时间将类似于2n-1吞吐时间。比较的数量会很高，但我不在乎，因为最终吞吐时间很快。并行算法分析
因此，本质上，是否存在对总体平行性能时间的共同分析？如果是这样，只要给我一些关键条款，我会从谷歌学习其余的。
算法分析并不意味着给出实际运行时间。这就是基准。分析告诉你程序中有多大的相对复杂性，但该程序的实际运行时间取决于许多其他因素，严格分析不能保证真实世界的时间。例如，如果您的操作系统决定暂停您的程序以安装更新，会发生什么情况？你的运行时间将被拍摄。由于计算机系统的复杂性（内存页面错误，虚拟机垃圾收集，IO中断等），即使反复运行相同的程序也会产生不同的结果。分析不能考虑到这些。
这就是为什么并行处理通常不会在分析过程中考虑的原因。 “并行化”程序组件的机制通常在代码外部，通常基于调度算法。我不知道有一个很好的方法来做静态分析。再一次，你可以运行一系列的基准测试，这会给你一个平均的运行时间。
我们通过并行步骤获得的时间效率可以通过round complexity来衡量。每一轮由同时发生的平行步骤组成。通过这样做，我们可以看到吞吐时间的有效性，在我们习以为常的类似分析中。
你有关于此的任何其他信息？我认为这很有趣，但我从未听说过。 – RustyTheBoyRobot
研究分布式计算。我认为麻省理工学院的教授南希·林奇有一本好书。一般的概念是用于类似的速度处理器，或基于组中最慢的，允许每个处理器在算法中至少进行一个步骤。 –
并行编程在这里有点红鲱鱼。 仅在大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而言，您的并行气泡排序可能会击败非平行（或甚至可能平行）的合并排序。虽然，与矩阵乘法不同，我认为范围会很小。
我的一位老教授在电子邮件中回复我说，在寻找这种情况下的“复杂性”。我试图看看我能否找到参考并验证它的用途。 –
在同时发生的并行步骤意义上的“圆”。说得通。 –
这听起来很像在“算法导论”一书中称为span的东西。它被定义为无限数量处理器上算法的运行时间。 –