算法思想之递归&分治&回溯_算法分治回溯csdn

参考文档

递归思想

什么样的情况下可以用递归？

1. 一个问题的解可以分解为几个子问题的解：子问题
2. 这个问题与分解之后的子问题，求解思路完全一样
3. 一定有一个最后确定的答案，即递归的终止条件

Master公式（计算递归复杂度）

注：使用Master公式分析递归问题复杂度时，各子问题的规模应该是一致的，否则不能使用Master公式

参数含义

a表示：递归的次数（生成的子问题数）
N表示：母问题的规模
b表示：子过程的样本量（当前母问题的子问题数量）
N/b表示：子问题的规模
O(N^d)表示：除了递归操作以外其余操作的复杂度

时间复杂度

举例分析master公式
1、递归求数组最大值

public static int maxNum(int[] arr, int L, int R){
    if(L == R) {
        return arr[L];
    }
    int mid = L + ((R - L) >> 1);
    int lMax = maxNum(arr, L, mid);
    int rMax = maxNum(arr, mid + 1, R);
    return Math.max(lMax, rMax); // O(N^d)=1
}
1
2
3
4
5
6
7
8
9

子问题数b=2，额外复杂度O(N^d)=O(1)，每次方法递归次数a=2
T(N)=2*T(N/2)+O(1)

2、斐波那契数列

    public static int fab(int n) {
        if (n <= 2) return 1; 
        return fab(n - 1) + fab(n - 2); // 递归次数 a=2
    }
1
2
3
4

T(N)=T(N-1)+T(N-1) +O（1）不符合master公式
斐波那契时间复杂度，通过画图能很好分辨为O(2^n)

递归的优化

斐波那契递归问题：

1. 每次执行递归方法会创建栈帧，jvm中栈帧的创建很消耗资源，上次递归依赖下次递归，导致上次资源不会释放
2. 时间复杂度大，O(2^n) 可优化到O(n)或者O(nlogn)

优化方式

1. 加入缓存：把我们中间的运算结果保存起来，这样就可以把递归降至为o(n)
2. 使用非递归（循环）。所有的递归代码理论上是一定可以转换成非递归的
3. 尾递归 ：函数最后一步调用另外一个函数

当编译器检测到尾递归时，覆盖当前栈帧，而不是去建立一个新的栈帧，这样只需要占用一个函数栈帧空间，防止了内存的大量浪费。

斐波那契优化

缓存优化

    private static int data[]; // 初始换全部是0
    /**
     * 缓存优化递归，用数组来做缓存
     * 时间复杂度：O(n) 空间复杂度：O(n)
     */
    public static int cacheFab(int n) {
        if (n <= 2) return 1; // 递归的终止条件
        if (data[n] > 0) {
            System.out.println(String.format("当前递查询缓存：f(%d)=f(%d)+f(%d)=%d", 
                    n, n - 1, n - 2, data[n]));
            return data[n];
        }
        System.out.println(String.format("当前递:f(%d)=f(%d)+f(%d)", n, n - 1, n - 2));
        int retult = cacheFab(n - 1) + cacheFab(n - 2);
        data[n] = retult; // 缓存记录计算结果
        System.out.println(String.format("当前归记录缓存：f(%d)=f(%d)+f(%d)=%d，缓存data[%d]=%d",
                n, n - 1, n - 2, retult,n,data[n]));
        return retult;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int retult = cacheFab(n - 1) + cacheFab(n - 2);归过程进行计算
测试用例

 public static void main(String[] args) {
        cacheFab(6);
 }
1
2
3

运行结果

当前递:f(6)=f(5)+f(4)
当前递:f(5)=f(4)+f(3)
当前递:f(4)=f(3)+f(2)
当前递:f(3)=f(2)+f(1)
当前归记录缓存：f(3)=f(2)+f(1)=2，缓存data[3]=2
当前归记录缓存：f(4)=f(3)+f(2)=3，缓存data[4]=3
当前递查询缓存：f(3)=f(2)+f(1)=2
当前归记录缓存：f(5)=f(4)+f(3)=5，缓存data[5]=5
当前递查询缓存：f(4)=f(3)+f(2)=3
当前归记录缓存：f(6)=f(5)+f(4)=8，缓存data[6]=8
1
2
3
4
5
6
7
8
9
10

可以看到减少了重复的计算

循环优化

使用循环模拟递归中的归过程，此时计算过程需要自己实现

1. 循环：是从初始值，往后计算每一个步骤的值，直到计算出当前步骤的值
2. 递归：从当前计算，往下调用自己【递过程】，找到知道的值，在往上返回计算【归过程】

public static int fab(int n) {
	// 递前置处理
    int res = fab(n-1) + f(n-2)
	// 归后置处理
	return res;
}
1
2
3
4
5
6

两种方式在于思维逻辑的区别

递归：从未知值，找已知，然后从已知到未知开始计算
循环：从已知开始计算，计算出未知值

// 时间复杂度：O(n)
public static int noFab(int n) {
        int a = 1; // f(1)  已知
        int b = 1; // f(2)  已知
        int c = 0; // f(n) = f(n-1)+f(n-2) 下次结果未知
        for (int i = 3; i <= n; i++) { // i=3,从第一个未知开始
            c = a + b; // 计算当前步骤结果
            a = b;
            b = c; // 作为下次的输入
            System.out.println(String.format("f(%d)=f(%d)+f(%d)=%d", i, i - 1, i - 2, c));
        }
        return c;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

画图演示
每一轮计算后 a = b、b = c

noFab(5)运行结果

-----f(2)、f(1)一开始就知道值了--------------
f(3)=f(2)+f(1)=2
f(4)=f(3)+f(2)=3
f(5)=f(4)+f(3)=5
1
2
3
4

尾递归优化

普通递归：一个大问题可以拆分为多个子问题，递归处理，复杂度指数级

int retult = fab(n - 1) + fab(n - 2);
利用递归函数进行计算，调用多次递归函数

尾递归：发现

int tailfab = tailfab(res, pre + res, n - 1);
计算放入递归函数中，只调用一次递归函数

/**
 * @param pre 上一次运算出来结果
 * @param res 上上一次运算出来的结果
 * @param n   是肯定有的
 */
public static int tailfab(int pre, int res, int n) {
    if (n <= 2) return res; // 递归的终止条件
    return tailfab(res, pre + res, n - 1); //倒着算
}

//--------用于测试分析改造的代码，尾递归要将调用放在最后-----------------------
public static int tailfab2(int pre, int res, int n,int m) {
    if (n <= 2) return res; // 递归的终止条件
    String s = "递：f(%d)=f(%d)+f(%d) ";
    System.out.println(String.format(s, n, n - 1, n - 2));
    String s2 = "递计算：pre+res=%d+%d=%d";
    System.out.println(String.format(s2, pre , res, pre + res ));
    int tailfab = tailfab2(res, pre + res, n - 1,m);
    String s3 = "归：f(%d)=f(%d)+f(%d)=%d";
    System.out.println(String.format(s3, n, n - 1, n - 2, pre + res));
    return tailfab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

tailfab2(1,1,5,5)运行结果

递：f(5)=f(4)+f(3) 
递计算：pre+res=1+1=2
递：f(4)=f(3)+f(2) 
递计算：pre+res=1+2=3
递：f(3)=f(2)+f(1) 
递计算：pre+res=2+3=5
归：f(3)=f(2)+f(1)=5
归：f(4)=f(3)+f(2)=3
归：f(5)=f(4)+f(3)=2
1
2
3
4
5
6
7
8
9

单向链表翻转

MyLinkedListFlip.java
MyLinkedList.java
MyNode.java

递归方式

    public MyNode reverse(MyNode curr) {
        if (curr == null || curr.next == null) {
            return curr;
        }
        MyNode next = curr.next;
        System.out.println(String.format("当前递,curr=%d,next=%d", curr.value, next.value));
        MyNode newHead = reverse(next); // 此处返回的是最后一个元素
        next.next = curr; // 指向前一个
        curr.next = null; // 前一个本身指向后一个，打断环形
        System.out.println(String.format("当前归,next=%d,curr=%d  ", next.value, curr.value));
        print(newHead);
        return newHead;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

测试用例

    public static void main(String[] args) {
        MyLinkedListFlip<Integer> linkedList = new MyLinkedListFlip<>();
        for (int i = 0; i < 5; i++) {
            linkedList.add(i);
        }
        linkedList.print();
        linkedList.reverse(linkedList.head);
        linkedList.print();
    }
1
2
3
4
5
6
7
8
9

运行结果

size=5  [0,1,2,3,4]
当前递,curr=0,next=1
当前递,curr=1,next=2
当前递,curr=2,next=3
当前递,curr=3,next=4
当前归,next=4,curr=3  
size=5  [4,3]当前归,next=3,curr=2  
size=5  [4,3,2]当前归,next=2,curr=1  
size=5  [4,3,2,1]当前归,next=1,curr=0  
size=5  [4,3,2,1,0]
1
2
3
4
5
6
7
8
9
10

非递归优化

    public MyNode noRecursionReverse(MyNode curr) {
        MyNode pre = null; // 当前节点curr的上一个节点
        // 每次遍历将当前节点指针指向上一个
        while (curr != null) {
            MyNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11

尾递归优化

  /**
     * 尾递归
     * @param pre 以前一个节点 开始为null
     * @param curr 当前节点  开始为头结点
     * @return
     */
    private MyNode tailReverse2(MyNode<E> pre, MyNode<E> curr) {
        if (curr == null) {
            return pre;
        }
        MyNode next = curr.next;
        curr.next = pre;
        return tailReverse2(curr, next);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14