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

106 阅读 0 评论 70 点赞

我是靠谱客的博主忧伤路灯，这篇文章主要介绍算法优化之非递归->递归->递归优化，现在分享给大家，希望可以做个参考。

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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) ;
以此类推得到递归方程：
程序代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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[ ]数组。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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；

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}