不同的二項式係數算法的效率比較

我比較了兩種算法來計算二項式係數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)，並且它使用乘法，這應該也會變慢。

那麼爲什麼動態編程版本要慢得多呢？

來源

2014-10-03 user3360041

我認爲應該是'O（k）'而不是'O（k^2）'。實際上，我計算了給定N＆K的係數計算所需的步數，「配方法」需要30步，「動態規劃」需要1116步。 – 2014-10-06 16:29:23

binomial_formula所寫的絕對不是O(k^2)。它只有一個尺寸爲k的單迴路，使其成爲O(k)。您還應該記住，在現代架構中，訪問內存的成本使任何單個指令的成本都相差數量級，並且動態編程解決方案在內存中讀取和寫入更多地址。第一個版本可以完全在幾個寄存器中計算。

請注意，您可以在您的線性版本通過識別真正改善是C（N，K）== C（N，NK）：

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; 
}

你應該記住，動態規劃僅僅是一個技術而不是銀彈。它不會神奇地使所有算法更快。

來源

2014-10-03 03:03:13 b4hand

首先算法

注意到
用途的空間

第二算法恆定量線性時間

注意到二次時間
用途的空間

在時間/空間方面，第一種算法更好，但第二種算法的優勢在於計算較小值的答案;它可以用作預處理步驟。

想象一下，您會收到n k表單的多個查詢，並且您被要求爲其中的每個查詢寫入n choose k。此外，想象一下查詢的數量很大（大約在n*n左右）。使用第一個算法需要O(nq) = O(n*n*n)，而使用第二個算法需要O(n*n)。

因此，一切都取決於你正在嘗試做的。

來源

2014-10-06 16:59:00 saadtaame

不同的二項式係數算法的效率比較

回答

相關問題