数据结构和算法分析

bilibili:: https://gitee.com/luzhenxiong/bilibili-leetcode
视频里程碑:: https://www.bilibili.com/video/BV1tU411U7SF

介绍

算法:: 是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令, 算法代表着用系统的方法描述解决问题的策略机制。
数据结构:: 计算机存储、组织数据的方式。希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题。

逻辑结构分类

逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类

集合结构: 数据元素除了同一个集合外，他们之间没有任何其他的关系。
线性结构: 数据元素之间存在一对一的关系
树形结构: 数据元素之间存在一对多的层次关系
图形结构: 数据元素是多对多的关系

物理结构

逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构，也可以叫做存储结构。

顺序存储结构

把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如数组就是顺序存储结构。

链式存储结构

是把数据元素存放在任意的存储单元里面, 这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

线性结构和非线性结构

线性结构

数组
队列
链表
栈

非线性结构

二维数组
多维数组
广义表
树结构
图结构

估计算法运行效率与时间复杂度

时间复杂度 - 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。
空间复杂度 - 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

算法的时间复杂度和空间复杂度合称为算法的复杂度。数量级常被称作大O记法(O指order)，记作O(f(n))。

常见的大O函数

常数级别-1: 普通语句(将两个数相加)
对数级别-logN: 二分策略(二分查找)
线性级别-N: 循环(找出最大元素)
线性对数级别-NlogN: 分治思想(归并排序)
平方级别-N^2: 双层循环(检查所有元素对)
立方级别-N^3: 三层循环(检查所有三元组)
指数级别-2^N: 穷举查找(检查所有子集)

常见的时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2logn) < O(n^3)

复杂问题的时间复杂度

O(n!) O(2^n) O(n^n)

小技巧

快速判断算法复杂度, 适用于绝大多数简单情况:

确定问题规模n
循环减半过程 -> logN
k层关于n的循环 -> n^k

常数级别

print("Hello World")

线性级别

n: int
for i in range(n):
    print('Hello World')

平方级别

for i in range(n):
    for j in range(n):
        print('Hello World')

立方级别

for i in range(n):
    for j in range(n):
        for i in range(n):
            print('Hello World')

对数级别

当算法过程出现循环折半的时候，时间复杂度式子中会出现logn

while n > 1:
    print(n)
    n = n // 2

空间复杂度

表示方式与时间复杂度完全一样

算法使用了几个变量: O(1)
算法使用了长度为n的一维列表: O(n)
算法使用了m行n列的二维列表: O(mn)

时间比空间重要，现在机器和硬件便宜

排序算法

基数排序

基数排序(radix sort)属于”分配式排序” (distribution sort), 又称”桶子法”，思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

思想

将所有的待比较数值统一设置位同样的数位长度，位数比较短的数前面补零，然后从最低位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列

例如, 数组[53, 3, 542, 728, 14, 214]

首先确定最大数是728(这个一定要确定, 通过循环数组找出来)
确定位数后，不足十位和百位的在前面补0
比较数组中的个位数, 按照顺序放到对应的桶中，每个桶都是一个一维数组，全部放进去后，再取出来重新排序。(得到542, 53, 3, 14, 214, 728)
然后再依次比较十位数，放到对应的桶中，没有十位的前面补0。(得到3, 14, 728, 542, 53)
依次比较百位数，放到对应的桶中，没有百位的补0。(得到3, 14, 53, 214, 542, 728)

冒泡排序

冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。

快速排序

对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

插入排序

插入排序属于内部排序，是对于排序的元素以插入的方式寻找该元素的适当位置, 以达到排序的目的。

选择排序

第一次从待排序的数据元素中选出最小(或最大)的一个元素, 存放在序列的起始位置，然后再从剩余的未排序元素中找到最小(或最大)的元素, 存放在已排序序列的末尾。以此类推, 直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

希尔排序

希尔排序(Shell’s Sort)是插入排序的一种，又称”缩小增量排序”(Diminishing Increment Sort), 是插入排序算法的一种更高效的改进版本。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

归并排序

归并排序(Merge Sort)是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

线性表

顺序表

以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中在逻辑结构上响应的数据元素存储

递归

参考资料

递归三原则

递归算法必须有基本情况(算法停止递归的条件);
递归算法必须改变其状态并向基本情况靠近;
递归算法必须递归地调用自己;

为了遵守第二条原则，必须设法改变算法的状态，从而使其向基本情况靠近。

链表

链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

栈

栈是限制插入和删除智能在一个位置上进行的线性表。其中, 允许插入和删除的一端位于表的末端，叫做栈顶(top), 不允许插入和删除的另一端叫做栈底(bottom)。对栈的基本操作有PUSH(压栈)和POP(出栈)，前者相当于表的插入操作(向栈顶插入一个元素)，后者则是删除操作(删除一个栈顶元素)。栈是一种后进后出(LIFO)的数据结构，最被删除的是最近压栈的元素。

队列

一种特殊的线性表, 特殊之处在于它只允许在表的前端(front)进行删除操作, 而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头

符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。

树

优点: 通过下标方式访问元素, 速度快，对于有序数组还可以使用二分查找提高检索速度

缺点: 如果要检索某个具体值, 或者插入值会整理移动，效率较低

树存储方式分析: 能提高数据存储，读取的效率，比如可以使用二叉树既可以保证数据检索速度，同时也可以保证数据的插入，删除，修改的速度。

堆

堆是一种特殊的树结构，堆的每个节点都满足以下条件:

是完全二叉树, 节点的左子树小于等于该节点的值
通常用数组来实现

二叉树

操作数据效率比较高

B树

通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(大小通常为4k)

2. 将树的M设置为1024, 在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中这样每个节点只需要一次I/O就可以完全载入

B+树

B树的变体，也是一种多路搜索树

搜素与B树基本相同，区别是B+树只有达到叶子节点才命中，其性能也等价于在关键字全集做一次二分查找，更适合文件索引系统

B*树

B+树的变体，在B+树的非根和非叶子节点再增指向兄弟的指针

赫夫曼树

给定N个权值作为N个叶子结点, 构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

丑数

把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上我们把1当做是第一个丑数。

assert 6 % 2 == 0
assert 7 % 2 != 0
assert 7 % 3 != 0
assert 7 % 5 != 0

递归

动态规划

核心思想:: 记住已有的结果，减少计算量。简单的做法是把计算结果存储在一张表中，并在计算新的结果之前，检查结果是否已在表中。如果是，就直接使用，而不是重新计算。
经典问题:: 找零时使用最少的硬币