💠

1. 数据结构和算法
- 1.1. 相关书籍和资源
- 1.2. 基础概念
  - 1.2.1. 算法的重要特征
  - 1.2.2. 时间复杂度
    - 1.2.2.1. 时间复杂度分析
    - 1.2.2.2. 最好最坏时间复杂度
    - 1.2.2.3. 平均时间复杂度
    - 1.2.2.4. 均摊时间复杂度
  - 1.2.3. 空间复杂度
- 1.3. 基础数据结构
  - 1.3.1. 线性表
    - 1.3.1.1. 数组
    - 1.3.1.2. 链表
    - 1.3.1.3. 数组和链表对比
  - 1.3.2. 树
- 1.4. 匹配算法
- 1.5. 排序算法
- 1.6. 搜索算法
- 1.7. 哈希算法 Hash
  - 1.7.1. Hash函数构造
  - 1.7.2. HASH 冲突
    - 1.7.2.1. 开放定址法
    - 1.7.2.2. 再 HASH 法
    - 1.7.2.3. 链地址/拉链法
    - 1.7.2.4. 公共溢出区
  - 1.7.3. 安全相关
1. 密码学
- 2.1. Diffie-Hellman Key Exchange算法
1. 实际问题
- 3.1. 斐波那契数列

💠 2024-12-04 16:30:24

数据结构和算法

数据结构是指一组数据的存储结构算法就是操作数据的方法数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上

基础概念

算法的重要特征

有穷性：保证执行有限步骤之后结束
确切性：每一步骤都有确切的定义
输入：每个算法有一个或多个输入，以刻画运算对象的初始情况。所谓零个输入是指算法本身舍弃了初始条件
输出：每个算法有一个或多个输出，显示对应输入数据加工后的结果。没有输出的算法是毫无意义的
可行性：在原则上算法能够精确地运行，进行有限次运算即可完成一次运算

时间复杂度

Java中的实践

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = O(f(n))
- T(n) 表示代码执行的时间；
- n 表示数据规模的大小；
- f(n) 表示每行代码执行的次数总和。

因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity) 简称时间复杂度

时间复杂度分析

只关注循环执行次数最多的代码
加法原则: 相加时的结果是: 总复杂度等于量级最大的那段代码的复杂度
乘法原则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度
- 常量阶 O(1)
- 对数阶 O(log n)
- 线性阶 O(n)
- 线性对数阶 O(n log n)
- 平方阶 O(n^2) 立方阶O(n^3 ) k次方阶 O(n^k) 用 ^ 表示次方
- 指数阶 O(2^n)
- 阶乘阶 O(n!)

O(1)

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

O(logn)、O(nlogn)

1
2
3
4


    int i=1;
    while (i <= n)  {
        i = i * 3;
    }

对数之间是可以互相转换的，log3 n 就等于 log3 2 * log2 n，所以 O(log3 n) = O(C * log2 n)，其中 C=log3 2 是一个常量。
基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))
所以，O(log2 n) 就等于 O(log3 n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

个人看法: 当循环中的循环变量的增长是以指数形式增长, 从而达到循环退出条件, 那么时间复杂度就是对数形式的

O(m+n)、O(m*n)

时间复杂度由两个数据的规模来决定, 原来的加法法则需要改为 T1(m) + T2(n) = O(f(m) + g(n)), 不清楚 m n 大小关系, 所以只能同时评估

四个复杂度分析方面的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度，最坏情况时间复杂度和平均情况时间复杂度

最好最坏时间复杂度

1
2
3
4
5
6
7
8
9


    // n 表示数组 array 的长度
    int find(int[] array, int n, int x) {
        int i = 0;
        int pos = -1;
        for (; i < n; ++i) {
            if (array[i] == x) pos = i;
        }
        return pos;
    }

顾名思义，最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。就像我们刚刚讲到的，在最理想的情况下，要查找的变量x正好是数组的第一个元素，这个时候对应的时间复杂度就是最好情况时间复杂度 O(1)。
同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。就像刚举的那个例子，如果数组中没有要查找的变量x，我们需要把整个数组都遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度 O(n)。

平均时间复杂度

要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值

(1+2+3+…+n+n) / (n+1) = n(n+3) / 2(n+1)

时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。

我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便, 假设在数组中与不在数组中的概率都为 1/2。
另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。
所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。
因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：

1 * 1/2n + 2 * 1/2n + n * 1/2n + 1/2 * n = (3n+1)/4

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。
引入概率之后，前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。
你可能会说，平均时间复杂度分析好复杂啊，还要涉及概率论的知识。实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。
很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    // array 表示一个长度为 n 的数组
    // 代码中的 array.length 就等于 n
    int[] array = new int[n];
    int count = 0;
    
    void insert(int val) {
        if (count == array.length) {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
        }

        array[count] = val;
        ++count;
    }

这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，
将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1)。
最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)。

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。
除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。
而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是

1 * 1/(n+1) + 1 * 1/(n+1)+…+ n * 1/(n+1) = O(1)

首先，find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。这是 insert()第一个区别于 find() 的地方。
我们再来看第二个不同的地方。对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。
针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


    // 全局变量，大小为 10 的数组 array，长度 len，下标 i。
    int array[] = new int[10]; 
    int len = 10;
    int i = 0;
    // 往数组中添加一个元素
    void add(int element) {
        if (i >= len) { // 数组空间不够了
            // 重新申请一个 2 倍大小的数组空间
            int new_array[] = new int[len*2];
            // 把原来 array 数组中的数据依次 copy 到 new_array
            for (int j = 0; j < len; ++j) {
            new_array[j] = array[j];
            }
            // new_array 复制给 array，array 现在大小就是 2 倍 len 了
            array = new_array;
            len = 2 * len;
        }
        // 将 element 放到下标为 i 的位置，下标 i 加一
        array[i] = element;
        ++i;
    }

最好是O(1)，最差是O(n), 均摊是O(1)

空间复杂度

类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

基础数据结构

线性表

数组, 链表, 队列, 栈

数组

一组连续的内存空间,存放一组相同数据类型的数据, 由于CPU访问存储器的局部性原理, 所以数组比链表高效

访问: 根据下标任意访问的时间复杂度为O（1）, 插入: 从最好O(1) 最坏O(n) 平均O(n) 删除: 从最好O(1) 最坏O(n) 平均O(n)

多次删除集中在一起，提高删除效率记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

1
2
3
4
5
6
7
8
9


    int main(int argc, char* argv[]){
        int i = 0;
        int arr[3] = {0};
        for(; i<=3; i++){
            arr[i] = 0;
            printf("hello world\n");
        }
        return 0;
    }

以上代码会死循环执行, 栈设计采用小端模式的系统才会出现

例子中死循环的问题跟编译器分配内存和字节对齐有关数组3个元素加上一个变量a 。4个整数刚好能满足8字节对齐所以i的地址恰好跟着a2后面导致死循环
如果数组长度为4 且循环5次则这里不会出现死循环。因为编译器64位操作系统下默认会进行8字节对齐变量i的地址就不紧跟着数组后面了。

存疑1: 当长度为4 无法解释. 压栈顺序: i，a[2]，a[1]，a[0], 所以 a[3]访问到的是i
存疑2: gcc有一个编译选项（-fno-stack-protector）用于关闭堆栈保护功能。默认情况下启动了堆栈保护，不管i声明在前还是在后，i都会在数组之后压栈，只会循环4次；如果关闭堆栈保护功能，则会出现死循环.

参考 GCC编译器堆栈保护技术 GCC 堆栈保护技术

容器和数组

众多语言都有对数组封装好的容器类

Java 中 ArrayList 和数组的对比

优势

对数组操作的细节进行封装,
支持动态扩容, 空间不够会扩容为原大小的1.5倍劣势
ArrayList 无法存放基础数据类型, 只能用包装类型, 这样就涉及到了自动拆装箱,影响性能
表示二维结构数据时, 没有数组直观

最好在创建 ArrayList的时候设置好初始大小,避免不必要的数据搬运对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

链表

单链表双向链表循环链表

Github: C语言代码实现个人

数组和链表对比

操作\时间复杂度	数组	链表
插入/删除	O(n)	O(1)
随机访问	O(1)	O(n)

分治算法动态规划最值极值不直接找问题, 而是根据你的输入, 和答案之前关系的规律

柯里化, continuation 高阶函数, 尾递归

树

Radix 树这是一种基于二进制表示的键值的查找树，尤其适合处理非常长的、可变长度的键值

并查集 DSU disjoint-set-union

Disjoint Set Union Data Structure | Baeldung on Computer Science
java - 并查集算法 - Algorithms, Part I, week 1 UNION-FIND - COURSERA-算法公开课-普林斯顿 - SegmentFault 思否

匹配算法

字符串相似度

字符串相似度匹配

字符串相似度计算：

Levenshtein算法编辑距离
三角比较算法
Diff Match Patch
余弦相似度 > 使用余弦相似度算法计算文本相似度 - 广告流程自动化

向量相似度

欧氏距离，余弦相似度，修正余弦相似度

向量相似度计算方法 | 沙舟的博客

排序算法

参考: 九种排序算法的可视化及比较

搜索算法

Trie 字典树

哈希算法 Hash

也称散列法关键字地址计算法

基本思想: 在元素的关键字 k 和元素的存储位置 p 之间建立一个对应关系 H, 使得 p = H(k)，则 H 被称为哈希函数

在创建哈希表时, 把关键字为 k 的元素放到地址为 H(k) 的单元
在查找时则根据关键字 k 计算出地址, 直接获取到元素, 时间复杂度达到 O(1)
MD5
SHA
- SHA家族算法有SHA-1、SHA-224、SHA-256、SHA-384和SHA-512（后四者通常并称SHA2）
CRC
- 循环冗余校验, CRC32（12、16、32等值均是指多项式的最高阶N次幂）
MurmurHash
- 是一种非加密型哈希函数，和其它流行哈希函数相比，对于规律性较强的 key 随机分布特性表现更良好，很多开源的软件项目使用（Redis，Memcached，Cassandra，HBase，Lucene）
Bcrypt 慢Hash函数
xxHash

smhasher Hash函数性能测试对比

Hash函数构造

设计哈希函数常考虑

哈希函数的时间复杂度
关键字长度
哈希表大小
关键字分布的情况
记录查找的频率

常见设计思路:

数字分析法 事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时, 可以从关键字中选出分布较均匀的若干位, 构成哈希地址

平方取中法 当无法确定关键字中哪几位分布较均匀时, 可以先求出关键字的平方值，然后依据需要取平方值的中间几位作为哈希地址
因为平方运算后中间几位和关键字中每一位都相关，所以散列程度比较高

分段叠加法 按哈希表地址位数, 将关键字分成位数相等的几部分, 后面多余的部分可以截断, 然后将这几部分移位相加或者折叠相加, 求得哈希值

除留余数法 哈希表长为m, p为小于等于m的最大素数, 哈希函数则是 H(k)=k%p 该方法容易产生哈希冲突

伪随机数法 直接使用随机数函数 H(k)=random(k)

JDK中的HashMap实现方式 取键值的hashCode, 然后高低16位做异或运算, 然后再与哈希表大小做与运算, 才得到哈希地址

HASH 冲突

参考: hash是如何处理冲突的?

参考: 一种高级的DoS攻击-Hash碰撞攻击 Application vulnerability due to Non Random Hash Functions

开放定址法

开放定址法有一个公式: Hi=(H(key)+di) % m; i=1,2,...,k(k<=m-1)
- 其中 m 为哈希表的表长 di 是产生冲突的时候的增量序列
线性探查法
- 如果di值可能为1,2,3,…m-1, 顺序查看表单元, 直到找到空单元。
平方探测法
- 如果di取1，则每次冲突之后，向后移动1个位置. 如果di取值可能为 1,-1^2,2^2,-2^2,...k*k,-k*k (k<=m/2)
伪随机探测
- di取值是伪随机数列

优点

缺点

当冲突多的时候数据容易堆集在一起，这时候对查找不友好；
删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不能真正删除结点；
如果哈希表的空间已经满了，还需要建立一个溢出表，来存入多出来的元素。

再 HASH 法

基本思想是构造多个不同的哈希函数, 当发生冲突时，使用第二个、第三个哈希函数计算地址，直到无冲突。

缺点

增加了时间复杂度

链地址/拉链法

将所有哈希地址为 i 的元素构成一个同义词链的单链表, 因此适用于频繁插入删除的情况

JDK中的HashMap（JDK8链表部分引入红黑树），Golang的map 均采用该方式

优点

处理冲突的方式简单，且无堆集现象，非同义词绝不会发生冲突，因此平均查找长度较短；
由于拉链法中各链表上的结点空间是动态申请的，所以它更适合造表前无法确定表长的情况；
删除结点操作易于实现，只要简单地删除链表上的相应的结点即可。

缺点

需要额外的存储空间

公共溢出区

假设哈希函数的值域为[0,m-1], 则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量 OverTable[0..v] 用以存储发生冲突的记录。

凡是和基本表发生冲突的元素一律填入溢出表

缺点

查找冲突数据的时候，需要遍历溢出表才能得到数据

安全相关

HASH攻击，例如针对Java中HashMap的算法，通过构造特定的参数，使得HashMap退化为链表，浪费服务器资源
不同的参数进入Hash函数运行时间会不一致，理论上利用这一点可以提高爆破密码的准确性，所以JDK中实现尽量保证了hash时间均匀

密码学

Diffie-Hellman Key Exchange算法

Whitfield Diffie 和 Martin Hellman ，他们于2015年获得了计算机科学领域的最高奖：图灵奖

码农翻身

最后神奇的魔法发生了，我们两个得到了同样的值 s = 10！

这个s 的值只有我们两个才知道，其实就是密钥了，可以用来做加密解密了（当然，这只是一个例子，实际的密钥不会这么短），我们俩的通讯从此就安全了。
- “数学家小帅哥说了，原因很简单，(gｘ mod p)ｙ mod p　和　(gｙ mod p)ｘ mod p　是相等的！ ”
- “那黑客不能从公开传输的 p = 17, g = 3, a = 6 , b = 12 推算出s = 10 吗？” 我问道。
- “当然不能，不过前提是需要使用非常大的p , x, y, 这样以来，即使黑客动用地球上所有的计算资源，也推算不出来。 ”

实际问题

例如存储一个部门关系, 上下级, 以及同级要有序, 并且, 这个关系树是能随意调整结构的, 每个节点和节点之间任意断开和连接

name/id, parent, index

斐波那契数列

神奇的斐波那契数列 | 斐波那契数列为什么那么重要

斐波那契数列: 递归, 离散数学, 斐波那契博弈数据结构: 斐波那契堆, 算法: 分治, 动态规划, 并行算法, 矩阵积, fft 操作系统线程, 线程级并行, openmp

二分搜索: 斐波那契数列实际上体现的是自然界某些情形下更本质的平权意识，尤其是当表面上的「对半法」实际上并不能做到平权时。自然情况下，对半分不一定就是平权，而黄金分割才是更本质意义下的平权
mid = (hi + low) /2 => mid = low + fib.get() - 1;

Contents