（n – 乘法）vs（n / 2 – 乘法+2加法）哪个更好？
我有一个C程序有n次乘法（单次乘法，n次迭代），我发现另一个逻辑有n / 2次迭代（1次乘法+2次加法）。 我知道两者都是O（n）的复杂性。 但就CPU周期而言。 哪个更快？
首先遵循Dietrich Epp的第一个建议 – 测量是（至少对于复杂的优化问题）唯一的方法。
现在，如果你想弄清楚为什么一个比另一个快，我们可以试试。 有两种不同的重要性能指标：延迟和相互吞吐量。 两者的简短摘要：
延迟：这是指令在依赖链中生成的延迟。 数字是最小值。 高速缓存未命中，未对齐和exception可能会显着增加时钟计数。 在启用超线程的情况下，在另一个线程中使用相同的执行单元会导致性能较差。 非正规数，NAN和无穷大不会增加延迟。 使用的时间单位是核心时钟周期，而不是时间戳计数器给出的参考时钟周期。
互惠吞吐量：同一线程中相同类型的一系列独立指令的每条指令的核心时钟周期的平均数。
对于桑迪桥而言。 add r, r/i吞吐量（进一步通知r =寄存器，i =立即，m =存储器）为0.33，而延迟为1。
imul r, r的延迟为3和rec。 吞吐量为1。
所以你看它完全取决于你的具体算法 – 如果你可以用两个独立的加法替换一个imul，你的算法的这个特定部分可以获得50％的理论加速（在最好的情况下显然加速~350％） ）。 但另一方面，如果你的添加添加了一个有问题的依赖，一个imul可能和一个添加一样快。
另请注意，我们忽略了所有其他复杂问题，如内存和缓存行为（通常会对执行时间产生更大影响的事情）或复杂的东西，如μop融合等等。 一般来说，唯一应该关心这些东西的人是编译器编写者 – 只是衡量他们努力的结果要简单得多;）
无论如何，如果你想要这个东西的良好列表，请参见此处 （上述延迟/记录吞吐量的描述也来自该特定文档）。
在您的计算机上测试。 或者，查看处理器的规格和猜测。
旧的逻辑不再适用：在现代处理器上，整数乘法可能非常便宜，在一些新的英特尔处理器上它是3个时钟周期。 在这些相同的处理器上增加1个周期。 但是，在现代流水线处理器中，由数据依赖性创建的停顿可能会导致添加时间更长。
我的猜测是，如果你正在进行折叠类型操作，N次加法+ N / 2次乘法比N次乘法慢，我猜测地图类型操作的反向。 但这只是猜测。
测试你是否想要真相。
但是：大多数这种简单的算法都受内存限制，两者的速度都相同。