数据结构与算法

什么是算法

1. 有具体的问题

2. 有设计解决这个问题的具体流程

3. 有评价处理流程的可量化指标

评估算法优劣的核心指标

1. 时间复杂度（流程决定）

2. 额外空间复杂度（流程决定）

3. 常数项时间（实现细节决定）

常数项时间

如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称这样的为常数时间操作。比如：数组的索引，无论下标为多少，始终都是计算偏移量 -> 索引这两个步骤。常见的常数时间操作有：

1. 常见的算数运算：+、-、*、/、%等

2. 常见的位运算：<<、>>、>>>、|、&、^等

3. 赋值、比较、自增、自减操作等

4. 数组的寻址操作

执行时间固定的操作都是常数时间操作，自行时间不固定的都不是常数时间操作。常数时间操作的时间复杂度都为 O(1)

时间复杂度

如何确定算法流程的总操作数量与样本数量之间的表达式？

1. 按照算法的最差情况计算

2. 将流程彻底拆分一个个基本动作，保证每个动作都是常数时间的动作

3. 假设数量为N，看基本动作与N之间的关系

---

如何确定时间复杂度？

当完成了表达式的建立，只要将高阶项留下即可。低阶项、高阶项系数全部去除，记为： O(高阶项)。

---

为什么可以忽略低阶项、高阶项系数？

当数据量足够大的时候，低阶项、高阶项对于算法效率的影响很小，算法的时间复杂度基本就由高阶项决定。

---

时间复杂度的意义？

衡量算法流程复杂度的指标，该指标只与数据量有关，与过程之外的优化无关。

额外空间复杂度

在实现算法流程的过程中，需要开辟一些空间来支持你的算法流程，另外：

1. 作为输入参数的空间，不算做额外空间

2. 作为输出结果的空间，也不算额外空间

除此之外的这部分空间就是额外空间。如果你的算法只需要开辟有限的几个变量，即与输入数据量无关，那么额外空间复杂度为O(1)。

算法问题最优解

一般情况下，认为解决一个问题的算法流程，在时间复杂度指标上，一定要尽可能的低，先满足了时间复杂度最低的指标后，使用最少的额外空间复杂度的算法流程，叫做这个算法问题的最优解。

一般说起算法最优解都是忽略常数项这个因素，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。

常见的时间复杂度

• O(1)

• O(logN)

• O(N)

• O(N*logN)

• O(N^2)，O(N^3) ... O(N^K)

• O(2^N)，O(3^N) ... O(K^N)

• O(N!)

对数器

通常我们在笔试的时候或者参加编程大赛的时候，自己实现了一个算法，但是不能够判断该算法是否完全没问题，如果在比赛平台上验证，通常只会告诉你有没有错误，出了错不会告诉你哪里有问题，对于排错来说是非常坑爹的，所以对数器就横空出世了，对数器就是用一个绝对OK的方法和随机器生成的样本数据进行合体，如果你的算法是没问题的，那么和对数器的这个百分之百正确的方法一个元素一个元素的比较，也一定是equals的。如果返回false，说明你的算法有问题。

---

什么是对数器？

1. 有一个你想要测的方法a；

2. 实现一个绝对正确但是复杂度不好的方法b；

3. 实现一个随机样本产生器；

4. 实现对比算法a和b的方法；

5. 把方法a和方法b比对多次来验证方法a是否正确；

6. 如果有一个样本使得比对出错，打印样本分析是哪个方法出错；

7. 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

---

针对插入排序的样例：

package class01;

import java.util.Arrays;

public class Code01_SelectionSort {

  // 1. 有一个你想要测的方法a；
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ N-1  找到最小值，在哪，放到0位置上
        // 1 ~ n-1  找到最小值，在哪，放到1 位置上
        // 2 ~ n-1  找到最小值，在哪，放到2 位置上
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

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

    // 2. 实现一个绝对正确但是复杂度不好的方法b；
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random()   [0,1)  
        // Math.random() * N  [0,N)
        // (int)(Math.random() * N)  [0, N-1]
        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 int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {

    // 3. 实现一个随机样本产生器；
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            selectionSort(arr1);
            comparator(arr2); 
      // 4. 实现对比算法a和b的方法；
      // 5. 把方法a和方法b比对多次来验证方法a是否正确；
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        selectionSort(arr);
        printArray(arr);
    }

}

什么是数据结构

数据结构的分类可以从两个角度分类：

1. 物理结构

2. 逻辑结构

其中物理结构可以分为：

1. 连续结构，比如数组

   连续结构在内存中是一块连续的内存；查找元素时，直接计算偏移量，速度较快；但是元素发生修改时，会重新移动内存，比较慢。

2. 跳转结构，比如单链表

   跳转结构中的每个元素中包含下上或者下个元素的内存地址；查找元素时，需要依次遍历寻找每个元素匹配，速度较慢；元素发生修改比较快，不用重新移动内存，直接更改指针即可。

如果按照逻辑结构划分，可以划分为如下结构：

Picture1.png