算法很美 笔记 2.递归与算法分析

2.递归与算法分析

递归

递归设计经验
找重复(子问题)
找重复中的变化量→参数
找参数变化趋势→设计出口

练习策略
循环改递归
经典递归
大量练习，总结规律，掌握套路
找到感觉，挑战高难度

1.求n的阶乘

/** * f1(n):求n的阶乘-->f1(n-1)求n-1的阶乘 * 找重复：n*(n-1)的阶乘,求n-1的阶乘是原问题的重复（规模更小）——子问题 * 找变化：变化的量应该作为参数 * 找边界：出口*/ static int f1(int n) { if (n == 1) return 1; return n * f1(n - 1); } 12345678910

2.打印i到j

/** * 打印i到j * 找重复： * 找变化：变化的量应该作为参数 * 找边界：出口*/ static void f2(int i, int j) { if (i > j) return; System.out.println(i); f2(i + 1, j); } 1234567891011

3.对数组元素求和

/** * 对arr的所有元素求和 * 找重复： * 找变化：变化的量应该作为参数 * 找边界：出口 * @param arr */ static int f3(int[] arr, int begin) { if (begin == arr.length - 1) { return arr[begin]; } return arr[begin] + f3(arr, begin + 1); } 12345678910111213

4.翻转字符串

//翻转字符串 static String reverse(String src, int end) { if (end == 0) { return "" + src.charAt(0); } return src.charAt(end) + reverse(src, end - 1); } 1234567

分解为:直接量+小规模子问题
分解为:多个小规模子问题（斐波那契）

5.斐波那契第n项

//斐波那契第n项 static int fib(int n){ if(n==1||n==2){ return 1; } return fib(n-1)+fib(n-2); } 1234567

斐波那契数列问题
等价于两个子问题:求前一项、求前二项
两项求和

6.辗转相除求最大公因数

//辗转相除求最大公因数 static int gcd(int m,int n){ if(n==0){ return m; } return gcd(n,m%n); } 1234567

7.递归形式插入排序

对数组0~倒数第一个排序等价于:
对数组的0~倒数第二个元素，这部分排序
然后把是后一个元素插入到这个有序的部分中

static void insertSort(int[] arr, int k) { if (k == 0) { return; } //对前k-1个元素排序 insertSort(arr, k - 1); //把位置k的元素插入到前面的部分 int x = arr[k]; int index = k - 1; while (index > -1 && x < arr[index]) { arr[index + 1] = arr[index]; index--; } arr[index + 1] = x; } 123456789101112131415

8.汉诺塔

1-N从A移动到B，C作为辅助
等价于：
1、1~N-1从A移动到C，B为辅助
2、把N从A移动到B
3、1-N-1从C移动到B，A为辅助

/** * 将N个盘子从source移动到target的路径的打印 * * N 初始的N个从小到达的盘子，N是最大编号 * source 原始柱子 * target 辅助的柱子 * help 目标柱子 */ static void printHanoiTower(int N, String source, String target, String help) { if (N == 1) { System.out.println("move " + N + " from " + source + " to " + target); } else { printHanoiTower(N - 1, source, help, target); // 先把前N-1个盘子挪到辅助空间上去 System.out.println("move " + N + " from " + source + " to " + target); // N可以顺利到达target printHanoiTower(N - 1, help, target, source); // 让N-1从辅助空间回到源空间上去 } } printHanoiTower(3, "A", "B", "C"); //从1-N从A移动到B，C为辅助

1234567891011121314151617181920

9.二分查找递归解法

全范围内二分查找
等价于三个子问题：
左边找（递归）
中间比
右边找（递归）
注意：左查找和右查找只选其一

static int binarySearch(int[] arr,int low,int high,int key){ if(low>high) return -1; int mid=low+((high-low)>>1); int midVal=arr[mid]; if(midVal<key){ return binarySearch(arr,mid+1,high,key); } else if (midVal>key){ return binarySearch(arr,low,mid-1,key); }else{ return mid; } } 1234567891011121314 找重复
1、找到一种划分方法
2、找到递推公式或者等价转换
都是父问题转化为求解子问题找变化的量
变化的量通常要作为参数找到出口
根据参数变化的趋势，对边界进行控制，适时终止递归

算法复杂度

n!的弱.上界是n^n，因此增长速度非常快，这意味着单位时间内可求解的问题很小，换言之，超慢

2^n这样的指数函数增长非常快，这种算法可以认为超慢

O(n2)和O(n3)增长很快，算法很慢，至少优化到nlgn，O(n2)的有冒泡排序，直接插入排序，选择排序

nlgn可以认为是及格的算法吧，一般分治法可以缩小层数为lgn，而每层的复杂度一般为O(n)，例如归并排序算法、快速排序算法

O (n)叫做线性算法，这种算法比较优秀，或者问题本身比较简单，比如求连续求和最大子数组的线性解

O(sqrt(n))当然比O(n)更快，不是没有，但这种很少

**lgn就是很优秀的算法了，比如二分查找法，**但是这种算法往往对输入数据的格式是有要求的，二分查找要求输入数据有序

还有一种是常量，无论规模怎么扩大，都花固定时间，这是为数极少的效率最高的算法了，多数是数据很规则

递归算法复杂度

递归关系结果举例T(n)=T(n/2)+O(1)T(n)=O(logn)二分查找，辗转相除最大公因数T(n)=T(n-1)+O(1)T(n)=O(n)线性查找T(n)=2T(n/2)+O(1)T(n)=O(n)T(n)=2T(n/2)+O(n)T(n)=O(nlogn)归并、快排T(n)=2T(n/2)+O(nlogn)T(n)=O(n(logn)^2)T(n)=T(n-1)+O(n)T(n)=O(n^2)选择排序、插入排序T(n)=2T(n-1)+O(1)T(n)=O(2^n)汉诺塔T(n)=T(n-1)+T(n-2)+O(1)T(n)=O(2^n)递归的斐波那契

排序算法的稳定性

稳定:如果a原本在b前面，而a=b ,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面，而a=b ,排序之后a可能会出现在b的后面。

算法稳定性

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性插入排序O(n^2)O(n^2)O(n)O(1)稳定希尔排序O(n^1.3)O(n^2)O(n)O(1)不稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定冒泡排序O(n^2)O(n^2)O(n)O(1)稳定快速排序O(nlog2n)O(n^2)O(nlog2n)O(nlog2n)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定桶排序O(n+k)O(n^2)O(n)O(n+k)稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定

题1:小白上楼梯(递归设计)

小白正在上楼梯，楼梯有n阶台阶，小白一次可以上1阶，2阶或者3阶，实现一个方法,计算小白有多少种走完楼梯的方式。

提示：设n阶台阶的走法数为f(n)。如果只有1个台阶，走法有1种（一步上1个台阶），即f(1)=1；如果有2个台阶，走法有2种（一种是上1阶，再上1阶，另一种是一步上2阶），即f(2)=2；如果有3个台阶，走法有4种（一种每次1阶，共一种；另一种是2+1，共两种；第三种是3，共1种），即f(3)=4；

当有n个台阶（n>3）时，我们缩小问题规模，可以这样想：最后一步有三种情况，走1步（之前上了n-1个台阶，走法为f(n-1)种），走2步（之前上了n-2个台阶，走法为f(n-2)种），走3步，（之前上了n-1个台阶，走法为f(n-3)种，f(n)=f(n-1)+f(n-2)+f(n-3),n>3

import java.util.Scanner; public class _小白上楼梯 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (true) { int N=sc.nextInt(); int re=f(N); System.out.println(re); } } private static int f(int n) { if(n==1){ return 1; } if(n==2){ return 2; } if(n==3){ return 4; } return f(n-1)+f(n-2)+f(n-3); } }

123456789101112131415161718192021222324

题2 :旋转数组的最小数字(改造二分法)

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入-一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 个旋转,该数组的最小值为1.

public class _旋转数组最小值 { static int f(int arr[]){ int be=0; int end=arr.length-1; //没有旋转直接返回第一个 if(arr[be]<arr[end]){ return arr[be]; } while (be+1<end){ int mid=be+((end-be)>>1); if(arr[mid]>=arr[be]){//左边有序，最小值在右边（无序） be=mid; }else{ end=mid; } } return arr[end];//最后剩两个元素，右边的位最小值 } public static void main(String[] args) { System.out.println(f(new int[]{4,5,6,2,3})); } }

1234567891011121314151617181920212223

题3 :在有空字符串的有序字符串数组中查找

有个排序后的字符串数组,其中散布着一些空字符串,编写-一个方法,找出给定字符串(肯定不是空字符串)的索引。

begin end

while

取中值对于出现空串的处理比较改变begin或end

return -1

public class _在有空字符串的有序字符串数组中查找 { static int index(String[] arr,String p){ int begin=0; int end=arr.length-1; while(begin<end){ //取中值 int mid=begin+((end-begin)>>1); //对于出现空串的处理 while(arr[mid].equals("")){ mid++; if(mid>end){//防止死循环 return -1; } } //比较改变begin或end if(arr[mid].compareTo(p)>0){ end=mid-1; }else if(arr[mid].compareTo(p)<0){ begin=mid+1; }else{ return mid; } } return -1; } public static void main(String[] args) { String[] arr = {"a", "", "ac", "", "ad", "b", "", "ba"}; int res = index(arr, "abc"); System.out.println(res); } }

123456789101112131415161718192021222324252627282930313233

题4 :最长连续递增子序列(部分有序)

(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入: [1,3,5,4,7] 输出: 3 解释: 最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 1234

输入: [2,2,2,2,2] 输出: 1 解释: 最长连续递增序列是 [2], 长度为1。 123

public class _最长连续递增子序列 { static int findLengthOfLCIS(int[] nums) { if(nums.length == 0) return 0; int max = 0; int count = 1; for(int i=0;i<nums.length - 1;i++){ if(nums[i] < nums[i+1]){ count++; }else{ max = Math.max(count,max); count = 1; } } max = Math.max(count,max); return max; } public static void main(String[] args) { System.out.println(findLengthOfLCIS(new int[]{1,3,5,4,7})); } }

12345678910111213141516171819202122

题5:设计一个高效的求a的n次幂的算法

static int pow(int a, int n) { if (n == 0) return 1; int res = a; int ex = 1; //能翻 while ((ex << 1) <= n) { //翻 res = res * res; //指数 ex <<= 1; } //不能翻 //差n-ex次方没有去乘到结果里面 return res * pow(a, n - ex); } 123456789101112131415

相关知识

基于递归神经网络算法的电子物流配送系统配送路径优化
一文讲清小红书推荐算法的秘密
机器学习算法
CMOFPA:多目标花授粉算法
js植物算法
图像识别算法有哪些
改进的花朵授粉算法程序（Matlab）资源
适应性花朵授粉算法研究
重磅！花书《深度学习》，这份精炼笔记可能是最全面的
鸢尾花三种聚类算法（K

网址: 算法很美 笔记 2.递归与算法分析 https://www.huajiangbk.com/newsview541545.html

上一篇: 鼓楼中医医院带您认识神奇的五音疗

下一篇: 七叶一枝花