发布时间:2023-03-16 08:00
根据代码随想录博主整理的
主要是为了记录递归算法如何分析其性能,并如何根据其性能来优化递归算法。
递归算法的时间复杂度 = 递归的次数 * 每次递归的时间复杂度。
递归算法的空间复杂度 = 递归的深度 * 每次递归的空间复杂度。
计算整数x的n次方
int function(int x, int n) {
int ans = 1;
for(int i = 0; i < n; i++) {
ans = ans * x;
}
return ans;
}
时间复杂度为O(n),空间复杂度为O(1)。
int recursion(int x, int n) {
if (x == 0)
return 0;
if(n == 0)
return 1;// 整数(零除外)的0次方为1
if(n == 1)
return x;// 退出递归条件
return recursion(x, n - 1) * x;
}
时间复杂度 = 递归的次数 * 每次递归的时间复杂度 = O((n - 1) * 1) = O(n);
空间复杂度 = 递归深度 * 每次递归的空间复杂度 = O((n - 1) * 1) = O(n);
为了降低时间复杂度,那么就需要O(log n)复杂度,假设每次递归时间复杂度为常熟O(1),那么,递归次数就需要为m = log n次。因为2^m = n,那么每次递归都可以减半,这样就可以重复利用这次递归结果,大大降低时间复杂度。
int recursion2(int x, int n) {
if(x == 0)
return 0;
if(n == 0)
return 1;// 整数(零除外)的0次方为1
if(n == 1)
return x;// 退出递归条件
int temp = recursion1(x, n / 2);
if(n % 2 == 1) {
return temp * temp * x;// n为奇数时
}
return temp * temp;// n为偶数时
}
时间复杂度 = 递归的次数 * 每次递归的时间复杂度 = O((log n) * 1) = O(log n);
空间复杂度 = 递归深度 * 每次递归的空间复杂度 = O((n - 1) * 1) = O(n);
在使用递归时,需要注意,是否存在多余计算,如何减少重复计算部分,就可对此进行优化处理。
软考 信息系统管理工程师和系统集成项目管理工程师有什么区别?
论文阅读 A Data-Driven Graph Generative Model for Temporal Interaction Networks
a*算法流程图_对称加密与非对称加密算法原理详解(对称加密篇)
揭开服务网格~Istio Service Mesh神秘的面纱
一款相见恨晚SCI论文写作神器-phrasebank-润色英文表达
用python-OpenCV做一个魔方墙找茬 (3D视眼训练)
C#工控上位机实例_「C#上位机」西门子1200PLC实用定位控制程序案例