算法中时间复杂度分析
2012-04-22
求函数 1!+2!+....+n!
列出两种算法比较性能
方法一:
int fact1(int n)
{
int i, j, temp, s;
s = 0;
for (i=1; i<=n; i++)
{
temp = 1;
for (j=1; j<=n; j++)
{
temp = temp*j;
s += temp;
}
}
return s;
}
方法二:
int fact2(int n)
{
int i, j, temp, s;
s=0; temp=1;
for(i=1; i<=n; i++)
{
temp = temp*i;
s += temp;
}
return s;
}
可以看出 fact2 时间性能比 fact1 好.
然而, fact2 比 fact1 好的是怎么评估的哪?
估算算法的计算量:
首先,可以将 以上问题分为 乘法,加法与赋值计算.
#fact1 计算量为:
1+2+...+n = (1+n)n/2 #乘法计算量
1+1+...+1 = n #加法计算量
(1+n)n/2 + 2n + 1 #赋值运算计算量
#推出 fact1 计算量总和为
(1+n)n/2 + n + (1+n)n/2 + 2n + 1 = n*n + 4n + 1
#fact2 计算量为
1+1+....+1 = n #乘法计算量
1+1+....+1 = n #加法计算量
2n + 1 #赋值运算计算量
#推出 fact2 计算量总和为
n + n + 2n + 1 = 4n + 1
设 fact1 n = n1, fact2 n = n2. 当 n1 = n2 时
得出: n*n+4n+1 > 4n+1