c - 不同二项式系数算法的效率比较

Question

我比较了两种计算二项式系数 C(n, k) 的算法，如下所示:#1 是从二项式系数的公式定义推导出来计算的，#2 使用动态规划。

#include <stdio.h>
#include <sys/time.h>

#define min(x, y) (x<y?x:y)
#define NMAX 150    

double binomial_formula(int n, int k) {
  double denominator=1, numerator=1, i;
  for (i = 0; i< k; i++)
    numerator *= (n-i), denominator *= (i+1);
  return numerator/denominator;
}

double binomial_dynamic_pro(int n, int k) {
  double c[NMAX][NMAX];
  int i,j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= min(i, k); j++) {
      if (i == j || j == 0)
        c[i][j] = 1;
      else
        c[i][j] = c[i-1][j-1]+c[i-1][j];
    }
  }
  return c[n][k];
}

int main(void) {
  struct timeval s, e;
  int n = 50, k = 30;
  double re = 0;
  printf("now formula calc C(%d, %d)..\n", n, k);
  gettimeofday(&s, NULL);
  re = binomial_formula(n, k);
  gettimeofday(&e, NULL);
  printf("%.0f, use time: %ld'us\n", re,
         1000000*(e.tv_sec-s.tv_sec)+ (e.tv_usec-s.tv_usec));

  printf("now dynamic calc C(%d, %d)..\n", n, k);
  gettimeofday(&s, NULL);
  re = binomial_dynamic_pro(n, k);
  gettimeofday(&e, NULL);
  printf("%.0f, use time: %ld'us\n", re,
         1000000*(e.tv_sec-s.tv_sec)+ (e.tv_usec-s.tv_usec));
  return 0;
}

然后我用gcc编译，运行出来是这样的:

now formula calc C(50, 30)..
47129212243960, use time: 2'us
now dynamic calc C(50, 30)..
47129212243960, use time: 102'us

这些结果出乎我的意料。我认为动态规划应该更快，因为它是 O(nk)，但是公式的方法应该是 O(k^2) 并且它使用乘法，应该是也会慢一些。

那么为什么动态规划版本要慢这么多呢？

Answer 1

binomial_formula 绝对不是 O(k^2)。它只有一个大小为 k 的循环，使其 O(k)。您还应该记住，在现代体系结构中，内存访问的成本比任何单个指令的成本都要小一个数量级，并且您的动态编程解决方案会在内存中读取和写入更多地址。第一个版本可以完全在几个寄存器中计算。

请注意，您实际上可以通过认识到 C(n,k) == C(n, n-k) 来改进您的线性版本:

double binomial_formula(int n, int k) {
  double delominator=1, numerator=1, i;
  if (k > n/2)
      k = n - k;
  for (i = 0; i< k; i++)
    numerator *= (n-i), delominator *= (i+1);
  return numerator / delominator;
}

您应该记住，动态规划只是一种技术，而不是 Elixir 。它不会神奇地使所有算法更快。