我有一个C程序，它有n次乘法(n次迭代的单个乘法)，我发现另一个逻辑有n/2次迭代(1次乘法+ 2次加法)。我知道复杂度都是O(n)而是在CPU周期方面。
在您的计算机上测试。或者，看看你的处理器的规格，猜猜看。
旧的逻辑不再适用:在现代处理器上，整数乘法可能非常便宜，在一些新的英特尔处理器上，它是3个时钟周期。在相同的处理器上，加法是1个周期。然而，在现代的流水线处理器中，由数据依赖关系造成的停顿可能会导致添加操作花费更长的时间。
我的猜测是N个加法+ N/2个乘法比N个乘法要慢，如果你做的是折叠类型操作，我猜映射类型操作正好相反。但这只是一个猜测。
如果你想知道真相就测试。
然而:大多数如此简单的算法都是内存限制的，并且两者的速度相同。
首先遵循Dietrich Epp的第一个建议-测量是(至少对于复杂的优化问题)唯一确定的方法。
如果你想知道为什么一个比另一个快，我们可以试试。有两种不同的重要性能度量:延迟和对等吞吐量。两者的简短总结:
Latency:这是指令在a中产生的延迟依赖链。这些数字是最小值。缓存错过,不对齐和异常可能会增加时钟计数很大。在启用超线程的地方，使用相同的另一个线程中的执行单元导致较差的性能。非正常数字、NAN和无穷大不会增加延迟。的使用的时间单位是核心时钟周期，而不是参考时钟周期由时间戳计数器给出。
互反吞吐量:每个内核时钟周期的平均数量指令为一系列同类的独立指令在同一个线程中
对于Sandy bridge, add r, r/i(进一步说明r=register, i=immediate, m=memory)的rec吞吐量为0.33，而延迟为1。
imul r, r的延迟为3,rec吞吐量为1。
因此，正如你所看到的，它完全取决于你的特定算法-如果你可以用两个独立的加法替换一个imul，你的算法的这一部分可以获得50%的理论加速(在最好的情况下明显加速~350%)。但另一方面，如果你添加了一个有问题的依赖项，一个imul可能和一个add一样快。
还要注意，我们已经忽略了所有额外的复杂性，如内存和缓存行为(通常会对执行时间产生非常非常大的影响)或复杂的东西，如μ op融合等。一般来说，唯一应该关心这些东西的人是编译器编写者——仅仅衡量他们努力的结果要简单得多;)
无论如何，如果你想要一个很好的这些东西的清单，看看这里(上面的延迟/rec的描述)。吞吐量也来自特定的文档)。