比较数学运算所花费的时间

Question

哪个实现会更快（理论上）-

long int total=0;
for(int n=1;n<=200000;)`
{ 
  total=total + n*(++n);
}

或

 long int total=0,sum=0;
for(int n=1;n<=200000;n++)`
{ 
  sum =sum+2*n;
  total=total + sum;
}

还是没有区别？

Answer 1

好吧，如果您是在算法方面讨论，那么第一个操作的复杂度要比第二个操作高。第一个操作的复杂度是 O(1)，而在第二种情况下它将是 O(n)。因此，当您的输入数量增加时，第一个可能比第二个花费的时间更少。延迟与执行操作所需的机器指令成正比。

Answer 2

您需要做的是明确编写要比较的两个程序。我想我知道你的意思，但如果你明确地写出来，那将是确定的。

假设我的猜测对你的意思是正确的，渐近时间复杂度对这个问题没有意义，因为没有自由变量。 n 是 "bound" 循环。如果您将 200000 替换为 M 那么讨论时间复杂度就有意义了。

您没有编写的两个程序中哪一个绝对速度更快的问题也是一个结构不佳的问题，因为答案很可能取决于上下文，正如 Mark Dickinson 所指出的那样。如果我对程序的猜测是正确的，那么算术运算的数量似乎大致相同。这可能意味着程序将运行在大约相同的时间内完成，也可能不会。我的猜测是时差是难以察觉的，但你为什么不试试呢？

最后，如果您要使用捷径 2(1)+2(2)+...+2(n)=n(n+1)，那么为什么不更进一步，使用捷径求和 1(2)+2(3)+...+n(n+1)？我们有

n(n+1) = (1/3)((n+1)^3 - n^3) - (1/3)

所以

1(2)+2(3)+...+n(n+1) 
= (1/3)(2^3-1^3) - (1/3) + (1/3)(3^3-2^3) - (1/3) + ... + (1/3)((n+1)^3-n^3) - (1/3)
= ((n+1)^3 - n - 1)/3

级数为"telescoping"，所以中间的立方项全部抵消。生成的表达式可以通过 5 次算术运算求值。

如果您在上面替换 n=200000，您会看到 int total 将溢出 32 位 int 类型。这是你的意图吗？

更新

我在我的系统上试过了（MacBook Air/Yosemite）。我比较的程序是

#include <stdio.h>

int main() {
  long int total;
  for (int trial=0; trial<1000; ++trial) {
    total = 0;
    for (int i=1; i<=200000; ++i) {
      total = total + i*(i+1);
    }
  }
  printf("answer is %ld", total);
  return 0;
}

和

#include <stdio.h>

int main() {
  long int total;
  int sum;
  for (int trial=0; trial<1000; ++trial) {
    total = 0;
    sum = 0;
    for (int i=1; i<=200000; ++i) {
      sum = sum + 2*i;
      total = total + sum;
    }
  }
  printf("answer is %ld", total);
  return 0;
}

我用 gcc -O 编译了它们，然后在 unix time 命令下运行它们。明显的赢家（在我的系统上，具有特定的体系结构，以及我所做的选择）是第一个程序。它大约需要 160 毫秒，而第二个大约需要 240 毫秒。第一个运行s 是第二个时间的 2/3。我对架构了解不够，无法推测造成差异的原因。

请注意，您程序中的行 total = total + i*(i++); 不正确。计算 i*i 然后递增 i。此外，该行和改进后的 total = total + i*(++i) 都会生成警告。

一些文体问题：我使用 i 而不是 n 作为循环索引，因此人们不会对 n 的含义感到困惑。我习惯性地使用 ++x 来递增 x 而不是 x++ 这可能会产生旧 x.

的不必要的临时副本

比较数学运算所花费的时间

comparing the time taken by mathematical operations

c

algorithm

math

performance

operation