c - (n - 乘法) vs (n/2 - 乘法 + 2 加法) 哪个更好？

Question

我有一个 C 程序，它有 n 次乘法(单次乘法和 n 次迭代)，我发现另一个逻辑有 n/2 次迭代(1 次乘法 + 2 次加法)。我知道两者都是 O(n) 的复杂性。但就 CPU 周期而言。哪个更快？

Answer 1

在您的计算机上进行测试。或者，查看您的处理器的规范并进行猜测。

旧逻辑不再适用:在现代处理器上，整数乘法可能非常便宜，在一些较新的 Intel 处理器上它是 3 个时钟周期。在这些相同的处理器上加法是 1 个周期。但是，在现代流水线处理器中，数据依赖性造成的停顿可能会导致添加操作花费更长的时间。

我的猜测是，如果您正在进行折叠类型操作，N 加法 + N/2 乘法比 N 乘法慢，而我猜想对于映射类型操作则相反。但这只是一个猜测。

测试你是否想要真相。

但是:大多数如此简单的算法都是内存限制的，并且两者的速度相同。