C#小技巧---递归优化的三种方式
2022/9/13 1:53:08
本文主要是介绍C#小技巧---递归优化的三种方式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
斐波那契数列
波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,是指这样一个数列
递推公式如图:
1.最常见递归算法
//最常见的递归 static int Fibo(int n) { if (n == 1 || n == 2) return 1; else return Fibo(n - 2) + Fibo(n - 1); }
但这种做法并不能完全解决问题,因为最大允许的递归深度跟当前线程剩余的栈空间大小有关,事先无法计算。如果实时计算,代码过于复杂,就会影响代码的可读性。所以,如果最大深度比较小,比如 10、50,就可以用这种方法,否则这种方法并不是很实用。
注意:递归代码要警惕重复计算
除此之外,使用递归时还会出现重复计算的问题。刚才我讲的第二个递归代码的例子,如果我们把刚才我讲的第二个递归代码的例子,如果我们把整个递归过程分解一下的话,那就是这样的:
n 越大,这段代码执行效率越低
执行结果:n:40,result:102334155,耗时:2470
我们会发现f(n)这个方法被调用了很多次,而且其中重复率非常之高,也就是说被重复计算了很多次,如果n稍微大一点这棵树会非常庞大。这里我们可以看出,每个节点就需要计算一次,总计算的次数就是该二叉树节点的数量,可见其时间复杂度为O(2^n),是指数级的,其空间复杂度也就是该二叉树的高度,为O(n)。这样来看,我们应该就清楚了,为什么这段代码效率如此低下了吧。
2.数组保存法
//数组保存法 static long Fibo2(int n) { long[] fib = new long[n]; fib[0] = 1; fib[1] = 1; for (int i = 2; i < n; i++) { fib[i] = fib[i - 2] + fib[i - 1]; } return fib[n - 1]; }
执行结果:n:40,result:102334155,耗时:0
时间复杂度和空间复杂度都为O(n)
3.滚动数组法
static long Fibo3(int n) { long first = 1; long second = 1; long third = 2; if (n <= 2) return 1; else { for (int i = 3; i <= n; i++) { third = first + second; first = second; second = third; } return third; } }
时间复杂度仍然为O(n),而空间复杂度为常量级别3,即空间复杂度为0
参考链接:https://mp.weixin.qq.com/s/UfNS80v_AdWGO7md83r8ng
这篇关于C#小技巧---递归优化的三种方式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2022-03-01沐雪多租宝商城源码从.NetCore3.1升级到.Net6的步骤
- 2024-12-06使用Microsoft.Extensions.AI在.NET中生成嵌入向量
- 2024-11-18微软研究:RAG系统的四个层次提升理解与回答能力
- 2024-11-15C#中怎么从PEM格式的证书中提取公钥?-icode9专业技术文章分享
- 2024-11-14云架构设计——如何用diagrams.net绘制专业的AWS架构图?
- 2024-05-08首个适配Visual Studio平台的国产智能编程助手CodeGeeX正式上线!C#程序员必备效率神器!
- 2024-03-30C#设计模式之十六迭代器模式(Iterator Pattern)【行为型】
- 2024-03-29c# datetime tryparse
- 2024-02-21list find index c#
- 2024-01-24convert toint32 c#