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

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

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

假设我的猜测对你的意思是正确的，渐近时间复杂度对于这个问题没有意义，因为没有自由变量。 n 被“绑定(bind)”到循环。如果将 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

该级数是“伸缩的”，因此中间的所有立方项都抵消了。生成的表达式可以通过 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 毫秒。第一个运行时间是第二个运行时间的 2/3。我对架构的了解还不够，无法推测造成差异的原因。

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

一些风格上的问题:我使用 i 而不是 n 作为循环索引，所以人们不会对什么是 n 感到困惑方法。我习惯性地使用 ++x 来递增 x 而不是 x++ ，这可能会对旧的 x 产生不必要的临时副本。