> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa.md).

# 数据结构与算法

## 什么是算法

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](/files/VtrZEPCgsnEKmccTHpSM)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.