从计算杨辉三角(Pascal Triangle)看算法优化

杨辉，字谦光，北宋时期杭州人。在他1261年所著的《详解九章算法》一书中，辑录了三角形数表，称之为“开方作法本源”图。 杨辉三角是一个由数字排列成的三角形数表，一般形式如下：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

杨辉三角最本质的特征是，它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。根据这一特征，我们可以用程序方便地实现输出杨辉三角。实现算法有很多，下面给出其中两种。

１、递归算法: F(i, j) = F(i-1, j-1) + F(i-1, j)

#include <stdio.h>

#include <stdlib.h>

long long pascal_triangle(int row, int col)
{
if (col == 1 || row == col)
return 1;
return pascal_triangle(row-1, col-1) + pascal_triangle(row-1, col);
}

int main(int argc, char *argv[])
{
int i, j;
int row = atoi(argv[1]);

for (i = 1; i <= row; i++)
{
for (j = 1; j <= i; j++)
printf("%u ", pascal_triangle_inc(i, j));
printf("/n");
}

return 0;
}

２、增量算法，使用一组数据保存已计算的值，占用O(n)额外存储空间

#include <stdio.h>

#include <stdlib.h>

long long pascal_triangle_inc(int row, int col, long long *a)
{
if (col == 1 || row == col)
{
a[row*(row-1)/2 + col - 1] = 1;
return 1;
}
//a[row-1][col-1] = a[row-2][col-2] + a[row-2][col-1];
a[row*(row-1)/2 + col - 1] = a[(row-1)*(row-2)/2 + col - 2] + a[(row-1)*(row-2)/2 + col - 1];
return a[row*(row-1)/2 + col - 1];
}

int main(int argc, char *argv[])
{
int i, j;
int row = atoi(argv[1]);
long long *a = (long long *)malloc((row*(row+1))/2 * sizeof(long long));
if (a == NULL)
{
perror("malloc");
return -1;
}

for (i = 1; i <= row; i++)
{
for (j = 1; j <= i; j++)
printf("%u ", pascal_triangle_inc(i, j, a));
printf("/n");
}

free(a);
return 0;
}

上面两种算法，递归算法简洁，但性能很大，存在太多的重复计算，当杨辉三角大时，计算非常慢。而增量算法，使用数组对先前计算结果进行保存，用于计算后续的数值，有效消除了冗余计算，以空间复杂性换取了计算复杂性，性能得到了很大的提升。在我自己的机器进行测试，递归算法计算row = 30时就比较困难了，而增量算法可以很快输出row = 1000的杨辉三角。当 row = 30时，两种算法的消耗时间分别如下：

time ./triangle 30

real 0m36.314s

user 0m21.201s

sys 0m0.004s

time ./triangle_inc 30

real 0m0.002s

user 0m0.000s

sys 0m0.000s

可见，增量算法在时间复杂性方面要远远优于递归算法，只是增加了一定的空间复杂性。所以，鱼和熊掌常常不可得兼。

其实，我先写了递归算法，发现其性能不可接受，于是给出了增量算法。数据结构和算法，是软件开发人员的基本功。当需要对程序性能进行调优时，就可以发现其巨大的威力。

(Aiguille LIU / 刘爱贵 / [e-mail])