算法中时间复杂度分析

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