匹配_KMP模式匹配算法：一
模式匹配 对子串的定位操作通常被称为串的模式匹配 简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止 朴素的模式匹配算法 KMP模式匹配算法 S串：abcdefgab T串...
大话数据结构_算法相关&&AVL&&B树相关 5
时间复杂度 O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) O(n^n) $$ O(1) < O(log_n)<O(n)<O(nlog_n)<O(n^2)<O(n^3)<O(2^n)&...
数学知识模板
试除法判定质数 试除法分解质因数 朴素筛法求素数 线性筛法求素数 试除法求所有约数 约数个数和约数之和 欧几里得算法 求欧拉函数 筛法求欧拉函数 快速幂 扩展欧几里得算法 高斯消元 递归法求组合数 通过预处理逆元的方式求组合数 Lucas定理 分解质因数法求组合数 卡特兰数 NI...
搜索与图论模板
树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 树与图的遍历 拓扑排序 时间复杂度O(n+m),n表示点数，m表示边数 朴素dijkstra算法 时间复杂度O(n*n+...
基础算法模板
快速排序 归并排序 整数二分算法 浮点数二分算法 高精度加法 高精度减法 高精度乘低精度 高精度除以低精度 一维前缀和 二维前缀和 一维差分 二维差分 位运算 双指针算法 离散化 区间合并
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 递归实现 插值查找 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较 $$ mid = \frac{(low+high)}{2} $$ $$ mi...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
排序_计数排序
简述 计数排序适用于对一定范围内的元素进行排序。 它的思路就是创建一个范围性的计数数组，用下标去对应元素的值，有几个元素，相应下面命中几次。然后根据元素命中次数对下标值进行一次输出，得到的序列就是有序的序列。 它是不需要进行元素比较。 注意： 当数列最大和最小值差距过大时，不适合...
搜索当前标签