共计 4130 个字符，预计需要花费 11 分钟才能阅读完成。
复杂度解说
算法效率
- 算法效率分为两种：工夫效率（工夫复杂度）和空间效率（空间复杂度）
- 它们别离掂量一个算法的运行工夫和所占的空间大小。
工夫复杂度
- 工夫复杂度计算的是一个函数中算法基本操作的执行次数。
- 工夫复杂度针对的是一整个函数。
工夫复杂度的计算方法（大 O 渐进表示法）
- 大 O 渐进表示法是一种估算：只取表达式中对后果影响最大的一项。
-
推导大 O 阶办法：
- 用数字 1 取代算数中的所有常数。
- 在批改后的算数中，只保留最高项。
- 如果最高阶存在且不是 1，则去除这个项的常数，失去的后果就是大 O 阶。
-
例如：
- 下列的工夫复杂度算数为：F(N) = 2*N + 10
- 所以大 O 阶表达式为：O(N)
void Fun1(int N)
{
int count = 0;
for (int i = 0; i < 2 * N; i++)
{++count;}
int M = 10;
while (M--)
{++count;}
printf("%d", count);
}- 留神：当函数中未知数有多个时
-
例如：
- 工夫复杂度表达式为：F(N) = M + N + 10 时，大 O 阶为 O(M+N) 或者 O(N)
- 工夫复杂度表达式为：F(N) = 1000 时，大 O 阶为 O(1)（第一步将所有常数用 1 代替）
- O(1) 示意的是算法中基本操作执行常数次，而不是真的只执行一次。
- 工夫复杂度表达式为：F(N) = M*M + N + 10 时，大 O 阶为 O(M^2)
- 工夫复杂度中：为了不便个别把 log2N（以 2 为底数）写作 logN（log3N 等就不会缩写了）
- 所谓的线性工夫复杂度就是指 O(N)。
空间复杂度
- 空间复杂度是对一个算法在运算过程中，长期占用的内存空间大小。
- 空间复杂度不是计算程序占用了多少个字节，而是计算长期变量的个数。
- 空间复杂度的计算方法也采纳大 O 渐进表示法。
- O(1) 代表常数个变量。
- 递归算法的空间复杂度就是递归的深度乘以每个算法的空间复杂度（每递归一次，就会在栈中创立一个长期的函数）
-
留神：
- 工夫是累计的，空间是能够复用的
- 创立局部变量后，在程序出大括号后，就会销毁。
程序表和链表
线性表
- 线性表是 n 个具备雷同个性的数据元素的无限序列
- 常见的线性表：程序表、链表、栈、队列等。
- 线性表在逻辑上是线性构造，但理论物理存储上通常是以数组和链式构造的模式存储的。
程序表和链表
-
程序表：
- 程序表实质就是数组，可能动静增长的，并且外面的数据是间断存储的（从左到右）
- 程序表的逻辑构造和物理构造是统一的，都是间断的。
-
链表：
- 链表的逻辑构造和物理构造不是统一的
- 物理上内存空间是按需分配，所以不存在空间节约，然而调配的空间是随机的。
- 单链表分为两局部，前一部分用来存储数据，后一部分用来存储指针，指向下一个节点
- 最初一个链表的指针指向 NULL。
程序表和链表的比拟
-
程序表的毛病：
- 程序表动静增容有性能耗费，增容个别是按两倍减少，可能有肯定水平的空间节约。
- 在程序表中插入数据时，须要移动数据，效率较低（O(N)）
-
程序表长处：
- 能够按下标进行随机拜访。
- 程序表的 CUP 高速缓存命中率比拟高。
- CPU 读取数据时，因为 CPU 的速度远高于内存，所以个别内存中的数据会提前被加载到高速缓存（Cache）中，而后 CPU 再从 Cache 中读取数据。
- 然而提前加载数据是按程序缓存的，所以程序表被提前加载时，命中率较高，因为它们的地址是间断的。而链表被提前加载时，因为地址不间断，所以命中率较低。（所谓的命中率就是被提前加载的数据就是 CPU 刚好须要的数据）
-
链表的毛病：
- 不反对下标的随机拜访。
- 链表的 CPU 高速缓存命中率较低，而且可能会造成缓存净化。
-
链表的长处：
- 按需申请内存，须要存一个数据，就申请一个内存，不存在空间节约。
- 在链表中插入删除数据时，不须要移动数据，效率高。
链表分类
-
链表分为：
- 单链表带头循环、单链表带头不循环、单链表不带头循环、单链表不带头不循环。
- 双链表带头循环、双链表带头不循环、双链表不带头循环、双链表不带头不循环。
-
理论中次要应用两种链表
- 无头单向链表：构造简略，个别不会独自用来存储数据，理论中更多的是作为其余数据结构的子结构。
- 带头双向链表：构造最简单，个别独自存储数据。
-
所谓的带头和不带头：
- 带头链表：是链表在首节点之前设置的一个头节点，然而它不存储无效数据，只是它的指针指向首节点。
- 头结点的作用：是为了不便对链表的操作。保障链表中每个元素都有一个前驱。
单链表定义方法
struct SListNode
{
int date; // 前一部分存储数据
struct SListNode* next; // 后一部分存储下一个节点的指针
}双链表定义方法
struct ListDouble {
struct ListDouble* prev; // 寄存上一个结点的地址
struct ListDouble* next; // 寄存下一个结点的地址
int val;
};栈和队列
栈
- 一种非凡构造的程序表，只容许在一端进行插入和删除元素，进行数据插入和删除的一端称为栈顶，另一端称为栈底。
-
栈中数据遵循后进先出准则。
队列
- 只容许在一端插入数据，在另一端删除数据。
- 队列遵循先进先出准则。
二叉树
树的概念
- 树是一种非线性的数据结构，它由 n 个无限节点组成一个具备档次关系的汇合，形态看着像一个倒挂的树。
- 有一个非凡节点，称为根节点，就是第一层的节点，它没有前驱节点。
- 树是递归定义的。
- 节点的度：一个节点含有的子节点个数。
- 叶节点或终端节点：度为 0 的节点。
- 父节点：一个节点含有子结点，那么这个结点就是根结点的父结点。
- 兄弟结点：雷同父结点的节点。
- 树的度：根结点的度就是树的度。
- 空树的层数为 0。
- 森林：多个不相交的树组成的汇合。
二叉树的概念
- 一个节点只能有两个子节点，然而这个两个子节点不肯定都存在。
- 例如：空节点是二叉树，一个节点也是二叉树。
- 对于任何一个二叉树，叶子节点（度为 0 的节点）永远比度为 2 的节点多一个。
满二叉树
- 它是一个二叉树，并且每层节点数都达到最大值
- 满二叉树的层数为 k，则节点总数为（2^k）-1。
- 每一层都有 2^(n-1) 个节点（也是每层最大节点数）（n 是层数）
齐全二叉树
- 齐全二叉树是效率很高的数据结构。
- 齐全二叉树的前 k - 1 层都是满的，最初一层能够不是满的。
- 然而最初一层必须是从左到右顺次排列的。
堆
- 堆在逻辑上是齐全二叉树构造。
- 堆只存在两种类型：大根堆和小根堆。
- 大根堆：父节点的值大于子节点的值。
- 小根堆：父节点的值小于等于子节点的值。
堆的下标法则
- 设父节点下标为 x，右边子节点下标为 y，左边节点下标为 z。
- y = x*2 + 1；
- z = x*2 + 2；
- x =（x – 1）/ 2 或者（y-1）/ 2；
二叉树的存储
- 二叉树个别用链式构造存储，即用链表来示意一个二叉树。
- 通常办法是：链表中每个节点由三个局部组成，数据域和左右指针。
- 左右指针别离用来指向该节点的左孩子和右孩子，数据域用来存储数据。
- 目前应用的都是二叉链表。
二叉树链式存储的遍历办法
-
深度优先遍历：
- 前序遍历：先拜访根，而后在拜访左子树，最初拜访右子树。
- 中序遍历：先拜访左子树，而后拜访根，最初拜访右子树。
- 后序遍历：先拜访左子树，而后拜访右子树，最初拜访根。
-
广度优先遍历：
- 层序遍历：从左到右一层一层的拜访。
排序算法
常见排序算法
- 插入排序：间接插入排序（实用于小量数据）、希尔排序（能够将大的数疾速地挪动都前面，实用于大量数据）
- 抉择排序：抉择排序、堆排序
- 替换排序：冒泡排序、疾速排序（挖坑法、前后指针法）
- 归并排序：归并排序
疾速排序
- 工夫复杂度 O(N * logN)
- 空间复杂度 O(logN)
- 稳定性：不稳固
如何取要害数 key
- 先取数组的第一个数、最初一个数和两头地位的数，而后取这三个数中不是最大也不是最小的那个数作为 key。
- 这种办法能够防止 key 间接选到最大值或者最小值。
左右指针法快排
- 一前一后两个指针，抉择一个要害数 key（个别是结尾位或者末位）
- 如果抉择结尾位为要害数 key，则让 end 向后先走，寻找比 key 小的数，找到小的数后停下。
- 而后 pre 向前走，寻找比 key 大的数，找到后进行。
- 而后替换 pre 的值和 end 的值，替换完后，end 持续向后挪动。
- 始终循环，直到 pre 和 end 相遇为止，相遇时的值肯定是比 key 小的，所以替换 key 和 pre 的值
- 这样，key 的数就会被挪动到整个数组的两头值地位，它右边的都比它小，左边的都比它大
- 最初应用递归。
挖坑法快排
- 另外定义一个变量 sum，用来保留第一个 pre，pre 的地位则空进去了。
- 而后 end 先向前挪动，寻找比 sum 小的数，找到后将 end 与 pre 替换，当初 end 的地位为空。
- 而后 pre 向前挪动，寻找比 sum 大的数，找到将 pre 与 end 替换，当初 pre 的地位为空。
- 而后再是 end 向前挪动………………
- 这样循环直到 pre 和 end 相遇为止，相遇时的地位为空，再将 sum 的值放到相遇的地位上。
- 这样这个数的右边都是比它小的数，左边都是比它大的数。
- 最初应用递归即可。
前后指针法快排
- 起始地位，pre 在第一位，end 在第二位。
- 而后 end 向后挪动，寻找比 key 小的值，找到后，pre++，而后替换 pre 和 end 的值。
- 而后持续 end 向后挪动，直到 end 拜访完为止
- 最初在替换 pre 和 key 的值
- 这样 key 这个数的右边都是比它小的数，左边都是比它大的数。
- 最初递归即可。
快排的小区间优化
- 当数据量很大时，在最初几层递归时，会呈现大量递归（呈现大量递归时可能会栈溢出），然而每个递归解决的数据较小。
- 所以为了防止最初几层的递归，在数据量较小时，间接应用插入排序
- 这样大数据处理的最初几层递归，则变为插入排序，能够缩小大量递归，升高解决工夫。
归并排序
- 工夫复杂度 O(N * logN)
- 空间复杂度 O(N)
- 稳定性：稳固
- 此办法须要借助另外一个长期数组。
- 将数组分为两局部，如果两边都是有序的，那么别离从两局部的起始地位开始比拟，将小的值尾插在新数组中，直到有一部分遍历完为止，再将另一部分剩下的尾插到新数组前面。
- 而后再将排序好的新数组赋值给原数组。
- 如果离开的两局部不是有序的，则别离再次差分，直到最初两局部都有序，执行上述步骤，将其排序。
- 因为判断是否有序比拟麻烦，所以个别不判断是否有序，而是将两局部都当做无序，进而始终拆分，直到最初两局部都只剩下一个数时进行尾插到新数组，而后再赋值给原数组，这样因为都是排序失去的，所以即便是无序的也会变成有序，所以能够不判断是否有序。
- 留神要开释长期数组。
排序算法的稳定性判断
- 数组中雷同的值，排序完后绝对程序不变的就是稳固，反之则为不稳固。
正文完
