算法优化之非递归->递归->递归优化

编程求1！+2！+3！+4！+…+20！的值。

1.非递归
主要是用双层循环来实现，temp用来记录阶乘，sum用来记录阶乘和，每次都要加上新加入的temp，逻辑很简单。

#include<stdio.h>
int main(){
int n,j,temp ;
double sum = 0;
for (n = 20; n >0 ; n--){
temp = 1;
for(j = 1; j <= n ;j++){
temp = temp*j;
}
sum = temp + sum;
}
printf("1！+2！+3！+4！+…+20！= %-20.0lfn",sum);
return 0;
}

2. 递归算法

• 找出F(n) = 1！+ 2！+ 3！+ 4！+…+ n！的递归数学表达式：
  n = 1时，F(1) = 1！= 1 ;
  n = 2时，F(2) = 1！+ 2！=3 ;
  n = 3时，F(3) = 1！+ 2！+ 3！= F(2) + (F(2) - F(1))*3 ;
  n = 4时，F(4) = 1！+ 2！+ 3！+ 4！= F(3) + (F(3) - F(2))4 ;
  ……
  n = n时，F(n) = 1！+ 2！+ 3！+ 4！+…+ n！= F(n-1) + (F(n-1) - F(n-2))n =(n+1) F(n-1) -nF(n-2) ;
  以此类推得到递归方程：
• 程序代码：

#include <stdio.h>
#include <windows.h>
long GetCPUTime()
{
static LARGE_INTEGER li = {0};
LARGE_INTEGER linow = {0};
if (li.QuadPart == 0)
QueryPerformanceFrequency(&li);
QueryPerformanceCounter(&linow);
return linow.QuadPart * 1000000 / li.QuadPart;
}
double F(int n)
{
if(n == 1)
{
return 1;
}
if(n == 2){
return 3;
}
else{
return (n+1)*F(n-1) - n*F(n-2);
}
}
int main(void)
{
int n,i,j;
long x,y;
double sum = 0;
sum = F(20);
printf("1!+2!+3!+...+20! = %-20.0lfn",sum);
for(i = 1; i <= 40; i +=5){
x = GetCPUTime();
for(j = 1000; j > 0; j--){
F(i);
}
y = GetCPUTime();
printf("n=%d：时间差（微秒） = %ldn",i,y - x);
}
return 0;
}

• 截图：你会发现很慢很慢很慢，于是我把规模改到了1，6，11，16…36,才短时间内得出来下面的截图：

• 时间复杂度分析：随着递归次数越多，时间复杂度达到了O(N的平方)。

3. 递归算法的优化
使用一个数组sum[ ]记录每一次求得的值，省去每次重复计算的麻烦。

• 此为改进的算法，只是多了个sum[ ]数组。

#include<stdio.h>
double sum[100]={0};
double F(int n){
if(n==1) {
sum[1] = 1; return sum[1];
}
if(n==2) {
sum[2] = 3; return sum[2];
}
if (sum[n] != 0){
return sum[n];
}
sum[n] = (n+1) * F(n - 1) - n * F(n - 2);
return sum[n];
}
int main(){
printf("1！+2！+3！+4！+ …+20！= %-20.0lfn",F(20));
system("pause");
return 0;
}

• 估算时间复杂度：
  当输入规模为1时，此算法需要执行1次；
  当输入规模为2时，此算法需要执行2次；
  当输入规模为3时，由于此前的F(2)和F(1)用了数组sum来存放了，故此时需要执行3次；
  ……
  以此类推
  ……
  当输入规模为n时，F(n) =(n+1)F(n-1)– nF(n-2)，函数需要执行n次，由于此算法中用数组sum(n-1)和sum(n-2)数组记录了计算过的F(n-1)和F(n-2)的值，并不需要重复计算，每次递归都只是计算了一遍，所估算F(n)的时间复杂度为O(n)。

• 验证时间复杂度：统计不同规模下计算函数值1000次的时间开销，并将GetCPUTime()的精度改为1微秒，以便更容易观察实际时间与规模之间的规律。分别尝试规模n为20,30,40,50,60；

#include<stdio.h>
#include <windows.h>
long GetCPUTime()
{
static LARGE_INTEGER li = {0};
LARGE_INTEGER linow = {0};
if (li.QuadPart == 0)
QueryPerformanceFrequency(&li);
QueryPerformanceCounter(&linow);
return linow.QuadPart * 1000000 / li.QuadPart;
}
double F(int n,double sum[]){
if(n==1) return 1;
if(n==2) return 3;
if (sum[n] != 0){
return sum[n];
}
sum[n] = (n+1) * F(n - 1, sum) - n * F(n - 2, sum);
return sum[n];
}
int main(){
int i,j;
long x,y;
for(i = 20; i <= 60; i +=10){
x = GetCPUTime();
for(j = 1000; j > 0; j--){
double sum[100]={0};
F(i,sum);
}
y = GetCPUTime();
printf("n=%d：时间差（微秒） = %ldn",i,y - x);
}
system("pause");
return 0;
}

• 时间复杂度
  
  根据上图画出散点图如下：
  

最后

以上就是忧伤路灯为你收集整理的算法优化之非递归->递归->递归优化的全部内容，希望文章能够帮你解决算法优化之非递归->递归->递归优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。