排序_桶排序
简述 桶排序需要创建若干个桶来协助排序。 所谓桶，每个桶bucket代表一个区间范围，里面可以承载一个或多个元素。 复杂度 名称 最好 平均 最差 空间 稳定性 桶排序 n+k n nlog(n) n 是 实现 算法导论 桶排序思想，假设对数组A[p...r]排序，首先将这些元素...
数据结构_最小优先级队列
概述 优先级队列是一种用来维护由一组元素构成集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字。一个最小优先级队列支持以下操作： insert(S,x):将元素x插入到集合S中 min(S)：返回S中具有最小关键字的元素 extract_min(S):去掉并返回S中具有...
排序_计数排序
简述 计数排序适用于对一定范围内的元素进行排序。 它的思路就是创建一个范围性的计数数组，用下标去对应元素的值，有几个元素，相应下面命中几次。然后根据元素命中次数对下标值进行一次输出，得到的序列就是有序的序列。 它是不需要进行元素比较。 注意： 当数列最大和最小值差距过大时，不适合...
匹配_朴素字符串匹配算法
字符串匹配 字符串匹配的形式化定义如下：假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和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)&...
BFS和DFS
BFS 概述 广度优先搜索（Breadth-First Search，简称 BFS）是一种遍历或搜索图或树数据结构的算法 它从根节点开始，沿着树的宽度遍历节点（即先访问同一层级的所有节点，再访问下一层级的节点） 在图中，BFS 从起始节点开始，探索所有邻居，然后依次遍历每个邻居的...
排序_插入排序
简述 插入排序思想，假设对数组A[p...r]排序: 维持不变式：设当前排序的元素是 A[q]，则保持A[p...q-1]为排好的，A[q]在A[p...q-1]中找到它的位置坐下 复杂度 O(n^2) 原地排序 实现
一些变量值交换的方法
第三个变量 实现 优点 简单易懂，逻辑清晰 缺点 需要额外的空间来存储临时变量 异或运算 实现 优点 不需要额外的空间 运算只使用基本的逻辑运算，适用于底层硬件编程 缺点 对大多数程序员来说，这种方法不如使用第三个变量的方式直观，容易引起误解 如果 a 和 b 是同一个变量，这种...
匹配_KMP模式匹配算法：二
预处理操作 参数 iterP_begin:模式序列P的起始迭代器 iterP_end:模式序列P的终止迭代器 解析 初始化 pai[1] = 0,k = 0 遍历(q从：2->m) 从2开始，因为Pk必须是Pm的真子集。 条件：k > 0 && p[k...
动态规划相关
概述 动态规划（Dynamic Programming，简称 DP）是一种通过分解问题来解决复杂问题的算法技术，特别适用于具有最优子结构性质的问题，即问题的最优解可以由其子问题的最优解构建而成 动态规划的核心思想是将问题分解成更小的子问题，并保存这些子问题的解，避免重复计算，从而...
搜索当前标签