# 数据结构与算法

## 什么是算法

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已经正确。

***

**针对插入排序的样例：**

```java
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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-cd36c9bb729a3a6d299f4d6b3242f8f534ce1685%2F1599638810-SZDwfK-Picture1.png?alt=media)