狄克斯特拉算法
概述 狄克斯特拉算法（Dijkstra's Algorithm）是一种用于计算单源最短路径的算法，适用于非负权重的有向图和无向图 对于狄克斯特拉算法而言，图必须有权重才行 如果图是无权图（即所有边的权重都相同，可以视为权重为 1） 可以使用广度优先搜索（BFS）来找到最...
排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...
大话数据结构_算法相关&&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)&...
排序_冒泡排序
简述 冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。 复杂度 名称 最好 平均 最差 空间 稳定性 冒泡排序 n n2 n2 1 是 理解 冒泡排序，有n个数字，就要进行n次大循环 每次大循环，会找到所有数里面的...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
基础算法模板
快速排序 归并排序 整数二分算法 浮点数二分算法 高精度加法 高精度减法 高精度乘低精度 高精度除以低精度 一维前缀和 二维前缀和 一维差分 二维差分 位运算 双指针算法 离散化 区间合并
匹配_KMP模式匹配算法：一
模式匹配 对子串的定位操作通常被称为串的模式匹配 简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止 朴素的模式匹配算法 KMP模式匹配算法 S串：abcdefgab T串...
数学知识模板
试除法判定质数 试除法分解质因数 朴素筛法求素数 线性筛法求素数 试除法求所有约数 约数个数和约数之和 欧几里得算法 求欧拉函数 筛法求欧拉函数 快速幂 扩展欧几里得算法 高斯消元 递归法求组合数 通过预处理逆元的方式求组合数 Lucas定理 分解质因数法求组合数 卡特兰数 NI...
动态规划一
动态规划 概述 动态规划通过将复杂问题分解为相互重叠的子问题，并利用存储中间结果来避免重复计算，从而高效解决具有最优子结构特性的问题 其核心在于 “状态定义” 和 “状态转移” 实现步骤 定义状态 (State Definition) 这是动态规划最基础且关键的一步。你需要定义一...
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 递归实现 插值查找 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较 $$ mid = \frac{(low+high)}{2} $$ $$ mi...
搜索当前标签