首页 计算机科学 算法与数据结构

# 递归 master 公式

剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上到底是怎么做的？

# master 公式的使用

T(N) = a*T(N/b) + O(N^d)
T (N): 母问题的数据量是 N 级别的
T (N/b): 子问题都是 N/b 的规模
a: 子问题的调用次数
O (N^d): 除去子问题的调用之外剩下的过程
无论如何切分，只要规模一样 就符合 master 公式
符合子问题规模等规模的递归可以用 master 公式

  1. log (b,a)>d-> 复杂度为 O (N^log (b,a))
  2. log (b,a)=d-> 复杂度为 O (N^d * logN)
  3. log (b,a)<d-> 复杂度为 O (N^d)

# 归并排序

  • 整体就是一个简单的递归，，左边排好序、右边排好序、让其整体有序。
  • 让其整体有序的过程里用了外排序方法
  • 利用 master 公式来求解时间复杂度
  • 归并排序的实质：时间复杂度 (N*logⁿ), 额外空间复杂度 O (N)
/**
 * @Author: LightRain
 * @Description: 归并排序 时间复杂度为 O (N*logⁿ)>O (N²)
 * 以为 O (N²) 浪费了大量的比较数据和空间，比较 N 才才会排好一个数
 * @DateTime: 2023-04-28 16:23
 * @Version：1.0
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{90, -90, 62, 92, 31, 78, 59};
        mergeSort(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
    }
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }
    private static void process(int[] arr, int l, int r) {
        // 如果一致则直接返回
        if (l == r) {
            return;
        }
        // 找数组的中点 l+(r-l)/2 ‘>>’代表位移法，位移 1 位也是除 2 的意思
        int mid = l + ((r - l) >> 1);
        // 先将左侧部分排好序 l->mid
        process(arr, l, mid);
        // 后将右侧部分排好序 mid+1->r
        process(arr, mid + 1, r);
        //
        merge(arr, l, mid, r);
    }
    private static void merge(int[] arr, int l, int m, int r) {
        // 辅助空间数组长度为 r-l+1 的长度
        int[] help = new int[r - l + 1];
        //help 数组专用下标
        int i = 0;
        // 将 p1 指向 l 的下标
        int p1 = l;
        // 将 p2 指向 mid+1 的下标
        int p2 = m + 1;
        //p1 和 p2 下标都不越界的情况下开始进行拷贝
        while (p1 <= m && p2 <= r) {
            //p1 和 p2 比较如果 p1 小于等于 p2 则先拷贝 p1 数据到 help [i] 位置然后 p1 下标 + 1，p1 不小于等于 p2 则将 p2 数据拷贝到 help [i] 位置然后 p2 下标 + 1，每进行一次 i 都会 + 1
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 如果 p1 下标没有越界就将 p1 剩下的数据一次拷贝到 help [i] 位置
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        // 如果 p2 下标没有越界就将 p2 剩下的数据一次拷贝到 help [i] 位置
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            // 将 help [i] 拷贝到原数组中去
            arr[l + i] = help[i];
        }
    }
}
# 归并排序的扩展 - 小和问题
  • 小和问题，在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
  • 求一个数组的小和。
  • 例：[1,3,4,2,5] 1 左边比 1 小的数没有，3 左边比 3 小的数有 1,4 左边比 4 小的数有 1,3，2 左边比 2 小的数有 1,5 左边比 5 小的数有 1,3,4。
  • 所以小和为 1+1+3+1+1+3+4+2=16
  • 逆序对问题，在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对。
/**
 * @Author: LightRain
 * @Description: 归并排序并求出小和
 * @DateTime: 2023-04-28 18:54
 * @Version：1.0
 **/
public class SmallSum {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 4, 2, 5};
        int i = smallSum(arr);
        System.out.println("小和 = " + i);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
    }
    private static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }
    /**
     * @Author: LightRain
     * @Date: 28/4/2023 下午 9:45
     * @Param: [arr, l, r]
     * @Return: int
     * @Description: 排序并求出小和
     * @since 17
     */
    private static int process(int[] arr, int l, int r) {
        // 如果一致则直接返回
        if (l == r) {
            return 0;
        }
        // 找数组的中点 l+(r-l)/2 ‘>>’代表位移法，位移 1 位也是除 2 的意思
        int mid = l + ((r - l) >> 1);
        // 左侧排序求小和的数量 + 右侧排序求小和的数量 + 左侧排好和右侧排好 merge 的小和的数量
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }
    private static int merge(int[] arr, int l, int m, int r) {
        // 辅助空间数组长度为 r-l+1 的长度
        int[] help = new int[r - l + 1];
        //help 数组专用下标
        int i = 0;
        // 将 p1 指向 l 的下标
        int p1 = l;
        // 将 p2 指向 mid+1 的下标
        int p2 = m + 1;
        // 小和数量
        int res = 0;
        //p1 和 p2 下标都不越界的情况下开始进行拷贝
        while (p1 <= m && p2 <= r) {
            // 左侧比右侧小才会产生小和 (r - p2 + 1)：代表当前右侧有多少个数比 p1 (p1 代表左侧) 要大 * arr [p1](左侧的数就是小和的数量)
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            //p1 和 p2 比较如果 p1 小于 p2 则先拷贝 p1 数据到 help [i] 位置然后 p1 下标 + 1，p1 不小于等于 p2 则将 p2 数据拷贝到 help [i] 位置然后 p2 下标 + 1，每进行一次 i 都会 + 1
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 如果 p1 下标没有越界就将 p1 剩下的数据一次拷贝到 help [i] 位置
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        // 如果 p2 下标没有越界就将 p2 剩下的数据一次拷贝到 help [i] 位置
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            // 将 help [i] 拷贝到原数组中去
            arr[l + i] = help[i];
        }
        return res;
    }
}
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 逆序对
 * @DateTime: 2023-04-28 18:54
 * @Version：1.0
 **/
public class ReverseSequencePair {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 4, 5, 0};
        int i = smallSum(arr);
        System.out.println("逆序对数量 = " + i);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
    }
    private static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }
    /**
     * @Author: LightRain
     * @Date: 28/4/2023 下午 9:45
     * @Param: [arr, l, r]
     * @Return: int
     * @Description: 排序并求出逆序对数量
     * @since 17
     */
    private static int process(int[] arr, int l, int r) {
        // 如果一致则直接返回
        if (l == r) {
            return 0;
        }
        // 找数组的中点 l+(r-l)/2 ‘>>’代表位移法，位移 1 位也是除 2 的意思
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }
    private static int merge(int[] arr, int l, int m, int r) {
        // 辅助空间数组长度为 r-l+1 的长度
        int[] help = new int[r - l + 1];
        //help 数组专用下标
        int i = 0;
        // 将 p1 指向 l 的下标
        int p1 = l;
        // 将 p2 指向 mid+1 的下标
        int p2 = m + 1;
        // 逆序对数量
        int res = 0;
        //p1 和 p2 下标都不越界的情况下开始进行拷贝
        while (p1 <= m && p2 <= r) {
            if (arr[p1] > arr[p2]) {
                res++;
                // 打印逆序对
                System.out.println(arr[p1] + " " + arr[p2]);
            }
            //p1 和 p2 比较如果 p1 大于 p2 则先拷贝 p1 数据到 help [i] 位置然后 p1 下标 + 1，p1 不小于等于 p2 则将 p2 数据拷贝到 help [i] 位置然后 p2 下标 + 1，每进行一次 i 都会 + 1
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 如果 p1 下标没有越界就将 p1 剩下的数据一次拷贝到 help [i] 位置
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        // 如果 p2 下标没有越界就将 p2 剩下的数据一次拷贝到 help [i] 位置
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            // 将 help [i] 拷贝到原数组中去
            arr[l + i] = help[i];
        }
        return res;
    }
}
# 荷兰国旗问题
# 问题一
  • 给定一个数组 arr，和一个数 num，请把小于等于 num 的数放在数组的左边。
  • 大于 num 的数放在数组的右边，要求额外空间复杂度为 O (1)，时间复杂度为 O (N)。
# 问题二 (荷兰国旗问题)
  • 给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间。
  • 大于 num 的数放在数组的右边，要求额外复杂度为 O (1)，时间复杂度为 O (N)。
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 快速排序 O (N*logⁿ)
 * @DateTime: 2023-05-05 17:09
 * @Version：1.0
 **/
public class QuickSort {
    public static void main(String[] args) {
        long startTime  = System.currentTimeMillis();
        int[] arr= new int[]{90, 61,92,31,78,59};
        quickSort(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
        long endTime  = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime ) + "ms");
    }
    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        partition(arr, 0, arr.length - 1);
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:28
     * @Param: [arr, l, r]
     * @Return: int []
     * @Description: 默认以 arr [r] 做划分，arr [r] --> p <p ==p >p
     * 返回等于区域 (左边界，又边界)，所以返回一个长度为 2 的数组 res,res [0] res [1]
     * @since 17
     */
    private static int[] partition(int[] arr, int l, int r) {
        // 小于区边界
        int less = l - 1;
        // 大于区边界
        int more = r;
        //l 表示当前数的位置 arr [r] --> 划分值
        while (l < more) {
            // 当前数小于划分值
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
                // 当前数大于划分值
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[]{less + 1, more};
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:38
     * @Param: [arr, i, j]
     * @Return: void
     * @Description: 交换
     * @since 17
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
# 快速排序
import java.util.Arrays;
/**
 * @Author: LightRain
 * @Description: 快速排序 O (N*logⁿ)
 * @DateTime: 2023-05-05 17:09
 * @Version：1.0
 **/
public class QuickSort {
    public static void main(String[] args) {
        long startTime  = System.currentTimeMillis();
        int[] arr= new int[]{90, 61,92,31,78,59};
        quickSort(arr);
        System.out.println("Arrays.stream(arr).toArray() = " + Arrays.toString(Arrays.stream(arr).toArray()));
        long endTime  = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime ) + "ms");
    }
    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:28
     * @Param: [arr, l, r]
     * @Return: void
     * @Description: arr [l.....r] 进行排序
     * @since 17
     */
    private static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            // 小于区 p [0]: 等于区域的左边界然后减 1 为小于区右边界
            quickSort(arr, l, p[0] - 1);
            // 大于区 p [1]: 等于区域的右边界然后加 1 为大于区左边界
            quickSort(arr, p[1] + 1, r);
        }
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:28
     * @Param: [arr, l, r]
     * @Return: int []
     * @Description: 默认以 arr [r] 做划分，arr [r] --> p <p ==p >p
     * 返回等于区域 (左边界，又边界)，所以返回一个长度为 2 的数组 res,res [0] res [1]
     * @since 17
     */
    private static int[] partition(int[] arr, int l, int r) {
        // 小于区边界
        int less = l - 1;
        // 大于区边界
        int more = r;
        //l 表示当前数的位置 arr [r] --> 划分值
        while (l < more) {
            // 当前数小于划分值
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
                // 当前数大于划分值
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[]{less + 1, more};
    }
    /**
     * @Author: LightRain
     * @Date: 5/5/2023 下午 6:38
     * @Param: [arr, i, j]
     * @Return: void
     * @Description: 交换
     * @since 17
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}