我刚刚读了一篇关于矩阵乘法突破的文章;一种算法是O（n^2.373）。但我想矩阵乘法是可以并行化的东西。那么，如果我们开始生产千分之一核处理器，这会变得无关紧要吗？事情会如何变化？
并行执行不会改变特定算法复杂性的基础 - 充其量，你只是花时间计算一些给定的大小，并除以内核数量。这可能会将给定大小的时间减少一个常数因子，但对算法的复杂性没有影响。
同时，并行执行有时会更改要用于特定任务的算法。一些在串行代码中运行良好的算法只是不能很好地拆分为并行任务。对于实际大小的问题，其他具有较高复杂性的问题可能更快，因为它们并行运行得更好。
对于数量非常多的内核，计算本身的复杂性可能变得次要，而不是简单地从所有内核获取必要的数据来进行计算。 BIG-O 的大多数计算在串行计算中都没有考虑这些影响，但它对于并行计算可能变得非常重要，特别是对于某些不能统一访问所有节点的并行机器模型。
如果量子计算有一天变得实用，那么是的，算法的复杂性将会改变。
同时，使用固定数量的处理器并行化算法只是按比例划分其运行时（在最好的情况下，当每个处理器执行的任务之间没有依赖关系时）。这意味着，将运行时除以一个常量，因此复杂性保持不变。
根据阿姆达尔定律，对于相同大小的问题，并行化将随着内核数量的增加而达到收益递减的点（理论上）。实际上，从一定程度的并行化来看，并行化的开销实际上会降低程序的性能。
然而，根据古斯塔夫森定律，随着问题规模的增加，内核数量的增加实际上有所帮助。这就是集群计算背后的动机。由于我们拥有更多的计算能力，我们可以借助并行化以更大的规模或更高的精度解决问题。
我们按原样学习的算法可能是可比的，也可能不是可相提并论的。有时，必须使用单独的算法来有效地并行执行相同的任务。无论哪种方式，都必须针对并行情况重新分析 Big-O 表示法，以考虑并行化对算法时间复杂度的影响。