算法初级-02-时间复杂度

年轻即出发...

简书：https://www.jianshu.com/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源码：https://github.com/zqtao2332

个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）

​ 咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。

最后：喜欢编程，对生活充满激情

---

---

本节内容预告

实例1：荷兰国旗问题

实例2：随机快速排序的细节和复杂度分析

实例3：堆排序的细节和复杂度分析

实例4：排序算法的稳定性及其汇总

实例5：工程中的综合排序算法

实例6：有关排序问题的补充

实例7：比较器的使用

实例8：桶排序、计数排序、基数排序的介绍

实例9：算法：给定排序数组，相邻两数的最大差值，时间复杂度O(N)

---

---

实例1

给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

问题二（荷兰国旗问题）
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

import java.util.Arrays;

/**
 * @description: 荷兰国旗问题
 * 给定一个数组arr，和一个数num，
 * 请把小于num的数放在数组的 左边，
 * 等于num的数放在数组的中间，大
 * 于num的数放在数组的 右边。
 *
 *
 * 思路
 *
 * 类似快排
 * less 指针指向小于 num 区域的最后一个数
 * more 指针指向大于 num 区域的第一个数
 * cur 指针指向当前数
 *
 * 如 ： 8 2 4 5 6 1 5   num = 5
 * 初始状态，小于区域没有元素， 大于区域也没有元素
 * less = -1
 * more = arr.length
 * cur = 0  --- > 8 位置
 *
 * arr[cur] 等于num 时 -->  不需要其他操作，只需要当前指针前移即可  cur++
 * arr[cur] 小于num 时 -->  交换 小于区域右边的一个数和 cur 指向的数，并且less++ , cur++
 * arr[cur] 大于num 时 -->  交换 大于区域左边的一个数和 cur 指向的数, 并且more--
 *
 *
 * 常规问题：将问题迁移到常规方面，即对任意数组的任意区域进行荷兰国旗，
 * 即数组 arr 的 L ~  R 区域进行荷兰国旗
 *
 * less = L -1
 * more = R + 1
 * cur = L
 * 算法过程和上述一致
 *
 * @version: 1.0
 */
public class Code_06_NetherLandsFlag {

    public static int[] netherLandsFlag(int[] arr, int num) {
        return partition(arr, 0, arr.length - 1, num);
    }

    /**
     * 任意一个数组的L，到R 区间都可以实现荷兰国旗
     * v2: 精简代码
     */
    public static int[] partition2(int[] arr, int L, int R, int num) {

        int less = L - 1; // 小于区域初始指针位置
        int more = R + 1; // 大于区域初始指针位置
        int cur = L;

        while (cur < more) {
            if (arr[cur] == num)
                cur++;
            else if (arr[cur] < num)
                swap(arr, ++less, cur++);
            else if (arr[cur] > num)
                swap(arr, cur, --more);
        }
//        return arr;
        // 返回等于区域的开始和结束位置
        return new int[]{less + 1, more - 1};
    }

    /**
     * 任意一个数组的L，到R 区间都可以实现荷兰国旗
     */
    public static int[] partition(int[] arr, int L, int R, int num) {

        int less = L - 1; // 小于区域初始指针位置
        int more = R + 1; // 大于区域初始指针位置
        int cur = L;

        while (cur < more) {
            if (arr[cur] == num) cur++;
            else if (arr[cur] < num) {
                swap(arr, less + 1, cur);
                less++;
                cur++;
            } else if (arr[cur] > num) {
                swap(arr, cur, more - 1);
                more--;
            }
        }
        return arr;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 5, 7, 9, 1, 19, 4, 32, 7, 7, 7};
        int[] landsFlag = netherLandsFlag(arr, 7);
        System.out.println(Arrays.toString(landsFlag));
        // [5, 2, 5, 1, 4, 7, 7, 7, 7, 32, 19, 9]
    }
}

实例2

随机快速排序的细节和复杂度分析

1. 经典快排：每次选取最后一个数作为参考点，有些数据状态不好的情况下，会变成O(N^N)的算法
2. 随机快排：在经典快排上进行参考点选取优化；随机选取数组中的一个数和最后一个数进行交换
3. 荷兰国旗优化：在随机快排上使用荷兰国旗方式进行进一步优化

可以用荷兰国旗问题来改进传统的快速排序
时间复杂度O(N*logN)，额外空间复杂度O(logN)

import java.util.Arrays;

/**
 * @description: 快速排序
 * 和经典版快排相比，这里采用荷兰国旗的解决方式，来进行快排升级
 */
public class Code_07_QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            int[] p = partition(arr, L, R);
            // 分治
            // 左半部分递归排序
            quickSort(arr, L, p[0] - 1);
            // 右边部分递归排序
            quickSort(arr, p[1] + 1, R);
        }
    }

    public static int[] partition(int[] arr, int L, int R) { // O(N)
        int less = L - 1;
        int more = R;
        while (L < more) {
            if (arr[L] < arr[R])
                swap(arr, ++less, L++);
            else if (arr[L] > arr[R])
                swap(arr, L, --more);
            else
                L++;
        }

        // 之前将R位置的直接置为了大于区间，现在需要交换到等于区间
        swap(arr, more, R);

        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {3,6,5,5,8,9,2,2,2,9,11};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

ps:有些算法在设计的过程中，需要绕开样本的状态，有两种常用的方式

• 随机打乱样本的状态，如（随机快排）
• 哈希函数打乱样本状态

归并排序和随机快排谁更有优势？

归并排序和随机快排在时间复杂度上都满足master公式，估计计算都是O(N*logN)，但是多数情况下随机快排要比归并排序更好！！

1. 随机快排额外空间复杂度O(logN)， 而归并排序额外空间复杂度O(N)
2. 随机快排实际的时间复杂度上的常数项要比归并排序的实际时间复杂度的常数项要小。

前面说过，在计算时间复杂度时是，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N), 那么时间复杂度为O(f(N))。

但是当估算的时间复杂度是一样时，查看两个算法的优劣需要具体考虑它实际的表达式，这里归并排序在归并过程中需要多次遍历（数组的回写），所有常数项要比随机快排要大。

实例3
堆排序的细节和复杂度分析
时间复杂度O(N*logN)，额外空间复杂度O(1)
堆结构非常重要

1. 堆结构的heapInsert与heapify
2. 堆结构的增大和减少
3. 如果只是建立堆的过程，时间复杂度为O(N)
4. 优先级队列结构，就是堆结构

package cn.zqtao.learn.day2;

import java.util.Arrays;

/**
 * @auther: zqtao
 * @description: 堆排序
 * 1、先将数组转化为大根堆（逻辑上的堆）
 * 2、交换大根堆的第一个元素和最后一个元素，那么最后一个元素一定的最大的数
 * 3、再对剩余的大根堆进行 heapify 调整，调整成为大根堆
 * 重复2、3过程，就是堆排序
 * @version: 1.0
 */
public class Code_08_HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int i = 0; i < arr.length; i++) {
            headInsert(arr, i);
        }

        // 交换首尾节点，大根堆长度减一
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);

        while (heapSize > 0){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 向大根堆中新增加一个元素
     * 完毕之后  0 ~  i 之间元素构成的就是一个大根堆
     *
     * @param arr
     * @param i   增加第 i 个元素为大根堆的节点
     * 任意节点 i 它的左孩子 2*i + 1
     *            它的右孩子2*i + 2
     *            它的父节点(i-1)/2
     */
    public static void headInsert(int[] arr, int i) {

        // 简洁方式
        while (arr[i] > arr[(i - 1) / 2]) { // 隐藏结束条件：i = 0时 arr[0] == arr[0]
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }

        // 找到父节点
//        int father = (i - 1) / 2;
//        while (arr[i] > arr[father]) {
//            swap(arr, i, father);
//            i = father;
//            // 继续找此节点的父节点
//            father = (i - 1) / 2;
//        }
    }

    /**
     * 调整变动过的大根堆为正确的大根堆
     * @param arr
     * @param index 需要开始调整的元素下标
     * @param heapSize 大根堆长度
     */
    public static void heapify(int[] arr, int index, int heapSize){
        // 找到当前节点的左孩子
        int left = 2 * index + 1;
        while (left < heapSize){
            // 找出左右孩子谁最大；先确认是否存在右孩子, 没有右孩子返回左孩子下标；有则比较返回最大的孩子的下标
            int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
            // 比较最大孩子和父节点值，返回最大下标
            largest = arr[largest] > arr[index] ? largest: index;
            // 如果最大的值下标，等于父节点本身，则直接break
            if (largest == index)
                break;
            swap(arr, largest, index);
            index = largest;
            left = 2 * index + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 5, 5, 8, 9, 2, 2, 2, 9, 11};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

实例4

排序算法的稳定性及其汇总

排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的

常见排序算法的稳定性

堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

实例5

工程中的综合排序算法

• 当数组的长度极低 < 60 插入排序，虽然算法复杂度是O(N * N)， 但是在样本极少的情况下，根本体现不出O(N ^2) 的缺点，反倒是插入排序的常数项系统极低，使得在样本极少的情况下插入排序非常快。
• 当数组的长度很大
  1. 当数组中的数据都是基础类型（int , double, float, char,,,），快速排序，基础类型数值稳定无意义。
  2. 当数组中的数组是自定义的类型（引用类型对象等），归并排序（O(NlogN), O(N)）保证排序稳定性

实例6

有关排序问题的补充：

1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不 需要掌握，可以搜“归并排序 内部缓存法”

2，快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜“01 stable sort”

3，有一道题目，是奇数放在数组左边，偶数放在数组右边，还 要求原始的相对次序不变，碰到这个问题，可以怼面试官。面试 官非良人。

实例7

比较器的使用

/**
 * @description:
 * @version: 1.0
 */

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code_09_Comparator {

    public static class Student {
        public String name;
        public int id;
        public int age;

        public Student(String name, int id, int age) {
            this.name = name;
            this.id = id;
            this.age = age;
        }
    }

    public static class IdAscendingComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o1.id - o2.id;
        }

    }

    public static class IdDescendingComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o2.id - o1.id;
        }

    }

    public static class AgeAscendingComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o1.age - o2.age;
        }

    }

    public static class AgeDescendingComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o2.age - o1.age;
        }

    }

    public static void printStudents(Student[] students) {
        for (Student student : students) {
            System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
        }
        System.out.println("===========================");
    }

    public static void main(String[] args) {
        Student student1 = new Student("A", 1, 23);
        Student student2 = new Student("B", 2, 21);
        Student student3 = new Student("C", 3, 22);

        Student[] students = new Student[]{student3, student2, student1};
        printStudents(students);

        Arrays.sort(students, new IdAscendingComparator());
        printStudents(students);

        Arrays.sort(students, new IdDescendingComparator());
        printStudents(students);

        Arrays.sort(students, new AgeAscendingComparator());
        printStudents(students);

        Arrays.sort(students, new AgeDescendingComparator());
        printStudents(students);


        System.out.println("测试 优先级队列  --->  实际上就是 堆");
        // 测试 优先级队列  --->  实际上就是 堆
        PriorityQueue<Student> heap = new PriorityQueue<>(new IdAscendingComparator());
        heap.add(student3);
        heap.add(student2);
        heap.add(student1);

        while (heap.size() > 0) {
            Student student = heap.poll();
            System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
        }

    }

}

实例8

桶排序、计数排序、基数排序的介绍
1，非基于比较的排序，与被排序的样本的实际数据状况很有关系，所 以实际中并不经常使用

2，时间复杂度O(N)，额外空间复杂度O(N)

3，稳定的排序

实例9

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序。

import cn.zqtao.learn.model.SortModel;

import java.util.Arrays;

/**
 * @description: 最大差值
 * 给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，
 * 且要求不能用非基于比较的排序。
 * <p>
 * 运用到了桶排序中的分桶的概念，但是它不是桶排序
 * 若有N个数，则准备N + 1 个桶
 * 找到N个数的最大值和最小值，0号位就放最小值，N 号位就放最大值
 * <p>
 * 记录每个桶的最大值，最小值，以及这个桶是否存在数
 * <p>
 * 每向一个桶添加一个数，都更新这个桶的最大值、最小值、是否有数
 * <p>
 * 最终，依次比较两个非空桶之间的 min  和  max 得到结果
 * @version: 1.0
 */
public class Code_10_MaxGap {
    public static int maxGap(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // 找到数组中的最大值和最小值
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }

        // 数组中的数都相同的情况，如：1 1 1 1 1
        if (max == min) return 0;

        boolean[] hasNum = new boolean[arr.length + 1];
        int[] maxs = new int[arr.length + 1];
        int[] mins = new int[arr.length + 1];

        int bid = 0;
        for (int i = 0; i < arr.length; i++) {
            bid = getBucketIndex(arr[i], arr.length, min, max);
            // 更新桶信息
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
            hasNum[bid] = true;
        }

        int res = 0;

        int lastMax = maxs[0];
        for (int i = 1; i < hasNum.length; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    /**
     * 确认每一个数在桶中所应该处于哪个位置
     *
     * @param num   需要确认的数
     * @param lenth 桶数量
     * @param min   最小值
     * @param max   最大值
     * @return
     */
    public static int getBucketIndex(long num, long lenth, long min, long max) {
        return (int) ((num - min) * lenth / (max - min));
    }

    // for test
    public static int comparator(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(nums[i] - nums[i - 1], gap);
        }
        return gap;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] randomArr = generateRandomArray(maxSize, maxValue);
            int[] arr1 = SortModel.copyArray(randomArr);
            int[] arr2 = SortModel.copyArray(arr1);
            if (maxGap(arr1) != comparator(arr2)) {
                if (!SortModel.isEqual(arr1, arr2)) {
                    succeed = false;
                    System.out.println("错误: " + Arrays.toString(randomArr));
                    System.out.println("待测方法结果：" + Arrays.toString(arr1));
                    System.out.println("正确方法结果：" + Arrays.toString(arr2));
                    break;
                }
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

}

以上都是算法课程学习总结