算法 算法的分析 时间分析 渐进记号 渐近紧确界记号： Θ(big-theta) 渐近紧确上界记号：O(big-oh) 渐近紧确下界记号：Ω(big-omege) 非渐近紧确上界： o(小-oh) 非渐近紧确下界： ω(小-omege) 常见复杂度 O(1) 常量级复杂度 O(n) 线性级 O(logn) 对数级 O(log3n) = O(C * log2n) 其他底的都可以转换成以2为底的 O(nlogn) 线性对数级 O(n^2) 多项式级，平方，立方，k次方级 O(2^n) 指数级，通常认为其是不可计算的，因为规模稍大效率就不行了 O(n!) 阶乘级, 全排列 递归的复杂度 递推公式 归并排序：T(n) = T(n/2) + T(n/2) + n T(1) = 1 T(n) = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n = 2^k * T(n/2^k) + k * n 由：T(1) = 1 n/2^k = 1 得： k=log(n) 带入上式得： T(1) = n + nlog(n) 递归树法(比较直观) 主定理法 空间分析 最好、最坏情况时间复杂度、平均情况时间复杂度(往往等于最坏情况时间复杂度) 摊还分析(平摊分析) 在n次操作中有一次耗时的操作O(n)，把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组**连续的操作**的均摊时间复杂度就是O(1) 典型的有：数组的扩张 算法下界的分析 决策树模型 查找 二分查找 迭代版 int binarySearch(arr, length, target){ int low = 0; int high = length - 1 if (arr[low] > target || arr[high] < target){ return -1 } //核心是每次循环一次就把搜索的区间缩小一半 while(low <= high) { //注意是<=,若是<的话，会漏掉最后只剩一个的情况 int middle = low+((high-low)>>1) if(target < arr[middle]) { high = middle - 1 //注意缩小区间的时候要加1减1 } else if ( target > arr[middle]) { low = middle + 1 } else { return middle } } return -1; } 递归版 private int bsearchInternally(int[] a, int low, int high, int value) { if (low > high) return -1; int mid = low + ((high - low) >> 1); if (a[mid] == value) { return mid; } else if (value < a[mid]) { return bsearchInternally(a, low, mid-1, value); } else { return bsearchInternally(a, mid+1, high, value); } } 布隆过滤器 主要的作用就是判断一个给定的值是否存在 bloom filter: False is always false. True is maybe true. 算法判断key在集合中时，有一定的概率key其实不在集合中 布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。 布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。当我们往 布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来 越高了。所以，对于无法事先知道要判重的数据个数的情况，我们需要支持自动扩容的功能。 排序 分析排序算法： * 排序算法的执行效率 1.最好情况、最坏情况、平均情况时间复杂度 2.时间复杂度的系数、常数 、低阶 3.比较次数和交换(或移动)次数 * 排序算法的内存消耗 * 原地排序(Sorted in place)。 * 排序算法的稳定性 * 内存排序or外部排序 计数排序(Counting sort) 原理就是用数组来把要排序的数字大小统计数量 适用于数据范围不大的场景中 基数排序 将整数按位数切割成不同的数字，然后按每个位数分别比较(位比较的时候可以用计数排序)。 典型问题：对10万个手机号码排序 桶排序 核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序 适合无法全部加载到内存的外部排序 快速排序 target: sort A[p..r] partition(A,p,r) // 分为三部分，【小于等于x】，【大于x】，【未处理的】 x = A[r] // 最后一个元素 i = p - 1 // 指向【小于等于x】最后一个元素 for j = p to r - 1 // j指向【未处理的】第一个元素 if A[j] <= x // 小的交换，大的直接加1 i++ exchange(A[i], A[j]) exchange(A[i+1], A[r]) return i + 1 递归版本 quick_sort(A,p,r) if p < r q = partition(A,p,r) quick_sort(A,p,q-1) quick_sort(A,q+1,r) 非递归版本 quick_sort(A,left,right) { PUSH(left,right); while(STACK_IS_NOT_EMPTY) { POP(lo,hi); if(lo < hi) { int mid = partition(A,lo,hi); PUSH(lo,mid-1); PUSH(mid+1,hi); } } } 归并排序 merge_sort(A,p,r) if p < r //终止条件,最终会下降到只剩一个元素 q = floor((p + r)/2) merge_sort(A,p,q) merge_sort(A,q+1,r) merge(A,p,q,r) merge(A,p,q,r) L = A[p:q],R = A[q+1:r] //copy array element to L and R i = 1,j = 1 for k = p to r if L[i] <= R[j] L R A A[k] = L[i] 5 2 2 i++ 6 3 3 else 5 A[k] = R[j] 6 j++ 堆排序(不稳定) heap_sort(A) build_max_heap(A) for i = A.length downto 2 exchange(A[1], A[i]) A.heap_size = A.heap_size - 1 max_heapify(A,1) 冒泡(bubbleSort) for(i = 0; i < n; i++){ // 每次循环把最大的顶上去 int sorted = 1; for(j = 0; j < n - i - 1; j++){ if (A[j] > A[j+1]){ sorted = 0; swap(&A[j], &A[j+1]); } } if(sorted) break; } 插入(跟抓扑克牌原理一样) insertion_sort(A) for j = 2 to A.length key = A[j] //待处理的元素 i = j - 1 while i > 0 and key < A[i] A[i + 1] = A[i] //往后挪一个元素 i-- A[i + 1] = key 选择排序 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序 每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾 选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。 顺序统计量 即寻找数组中第N个大的数字，Θ(n),以快排算法的parttion部分为模型，因为parrtion部分返回 的pivot就是它的下标的第几大的值 算法思想 递归 利:是递归代码的表达力很强，写起来非常简洁； 弊:就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用开销 关键步骤: 1. 找到如何将大问题分解为小问题的规律，比如：n规模的问题能不能通过n-1的规模(子问题)或多个n-x的规模之和来解决。 2. 并且基于此写出递推式 3. 然后再推敲终止条件，终止条件可以有好几个，这个是需要注意的，对应于上面的多个n-x的规模之和 4. 用几个小规模的问题验证一下有没有问题 5. 最后将递推公式和终止条件翻译成代码 典型问题： 求二叉树的节点数 O(log(n)) count_tree(Tree) if(Tree = NULL) return 0; return 1 + count_tree(Tree.left) + count_tree(Tree.right) 归并排序，快速排序 O(nlog(n)) 上台阶问题，等同于(斐波那契数列) O(2^n) 有n个台阶，每次你可以跨1个或者2个台阶，请问走这n个台阶有多少种走法？ n的问题规模可以通过子问题来求解 递推公式：f(n) = f(n-1) + f(n-2) #递归数会指数膨胀，假如上1级，则剩余台阶的方法数为f(n-1)；假如上2级，剩余台阶的方法数为f(n-2) 递归基：f(1) = 1; f(2) = 2; 因为问题规模被划分成两个，这两个都的解出才有结果 int f(int n) { if (n == 1) return 1; if (n == 2) return 2; return f(n-1) + f(n-2); } 减治法 每次问题的规模都缩小 分治法 将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后 再合并其结果，就得到原问题的解。 分治算法是一种处理问题的思想，递归是一种编程技巧 分解：将原问题分解成一系列子问题； 解决：递归地求解各个子问题，若子问题足够小，则直接求解； 合并：将子问题的结果合并成原问题。 分治能解决的问题满足的条件： 1.原问题与分解成的小问题具有相同的模式； 2.原问题分解成的子问题可以独立求解，子问题之间没有相关性 3.具有分解终止条件，也就是说，当问题足够小时，可以**直接求解**； 4.可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法 总体复杂度的效果了。 例子： 归并排序 统计一组数据中的逆序对个数 海量数据处理应用 将任务分配到分布的多台机器上并行的处理，最后再将结果合并在一起 MapReduce 框架只是一个任务调度器，底层依赖 GFS 来存储数据，依赖 Borg 管理机器。它从 GFS 中拿数据，交给 Borg 中的机器执行，并且时刻监控机器执行的进 度，一旦出现机器宕机、进度卡壳等，就重新从 Borg 中调度一台机器执行 最大子数组 find_max_crossing_subarray(A,low,mid,high) left_sum = null sum = 0 for i = mid downto low sum += A[i] if sum > left_sum or left_sum == null left_sum = sum max_left = i right_sum = null sum = 0 for j = mid + 1 to high sum += A[j] if sum > right_sum right_sum = sum max_right = j return (max_left, max_right, left_sum + right_sum) find_max_subarray(A,low,high) if hight = low return (low, high, A[low]) else mid = floor((low + high)/2) find_max_subarray(A,low,mid) find_max_subarray(A,mid+1,hight) find_max_crossing_subarray(A,low,high) 比较，然后返回最大的 回溯算法 很多时候都应用在“搜索”这类问题上 不过这里说的搜索，并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。 回溯算法非常适合用递归代码实现 基本思路是：寻找的问题解不满足时，回溯到上一步骤，继续问题的求解 回溯算法本质上就是穷举所有情况，然后对比得到最优解。优点在于其类似于摸着石头过河的查找策略，且可以通过剪枝 少走冤枉路。它可能适合应用于缺乏规律，或我们还不了解其规律的搜索场景中。 典型问题： 深度搜索 八皇后 ANSWER_COUNT = 0 MAXNUM = 4 # 检查当前坐标是否能放置queen # 只需检查当前坐标的↖↑↗这三个坐标上侧方向 # 因为本行的落子不受下一行的影响 # x第几行 y第几列 def check(x,y,chess): for i in range(x): # i [0,x) 行的值永远不会出界 # 检查竖向↑（只需检查当前行之上的行） if(chess[i][y]==1): return False # 检查左上斜方向↖ if(y-1-i >= 0): # if(chess[x-1-i][y-1-i] == 1): return False # 检查右上斜方向↗ if(y+1+i < MAXNUM): if(chess[x-1-i][y+1+i] == 1): return False return True # 打印棋盘 def print_chess(chess): print('answer {}:'.format(ANSWER_COUNT)) for i in range(MAXNUM): for j in range(MAXNUM): print(chess[i][j],' ',end='') print('\n') print('\n') # 递归求解8个queen的放置方式 def find_queen8(x,chess): global ANSWER_COUNT,MAXNUM # 临时棋盘，复制上一行的queen皇后落子后的棋盘 chess_temp = [[0 for col in range(MAXNUM)] for row in range(MAXNUM)] for i in range(MAXNUM): for j in range(MAXNUM): chess_temp[i][j] = chess[i][j] # x等于棋盘边界，代表已最后一行的queen已经落子，打印结果并返回 if(x == MAXNUM): ANSWER_COUNT = ANSWER_COUNT + 1 print_chess(chess_temp) return # 遍历当前行的每一列 for i in range(MAXNUM): if(check(x,i,chess_temp)): chess_temp[x][i] = 1 #从这一行返回分两种情况：1.遍历到最后一行找到结果 2.遍历某一行后都没有通过检查 find_queen8(x+1,chess_temp) chess_temp[x][i] = 0 #回溯到之前成功或失败的哪一步 def main(): #初始棋盘 chess = [[0 for col in range(MAXNUM)] for row in range(MAXNUM)] #从第0行开始 find_queen8(0,chess) #打印结果 print('求解{}皇后问题，共有{}个答案: '.format(MAXNUM, ANSWER_COUNT)) main() 动态规划 我们把问题分解为多个阶段(从第到高)，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的）， 然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。 适合问题 一个模型三个特征： 多阶段决策最优解模型、 最优子结构、 问题的最优解包含子问题的最优解，子问题的最优解推导父问题最优解，即后面阶段的状态可以通过前面阶段的状态推导出来 无后效性 重复子问题 方法： 1.带备忘录的自顶向下 2.自底向上 状态转移表法,通过画状态转移表来深刻理解问题所有状态的动态转移 回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码 状态转移方程法 找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码 某个问题如何通过子问题来递归求解，也就是所谓的最优子结构，比如锯钢条问题 r(n) = 状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程，那 动态规划问题基本上就解决一大半了，而翻译成代码非常简单 典型问题： 钢条切割问题， p:价格数组 n:切割总长度 r:最优解数组 cut_rod(p,n) // O(2^n) if n == 0 return 0 q = -∞ for i = 1 to n q = max(q,p[i] + cut_rod(p,n-i)) return q memoized_cut_rod(p,n) let r[0..n] be a new array for i = 0 to n r[i] = -∞ return memoized_cut_rod_aux(p,n,r) memoized_cut_rod_aux(p,n,r) if r[n] >= 0 return r[n] if n == 0 q = 0 else q = -∞ for i = 1 to n q = max(q,p[i] + memoized_cut_rod_aux(p,n-i,r)) r[n] = q return q bottom_up_cut_rod(p,n) let r[0..n] be a new array r[0] = 0 for j = 1 to n q = -∞ for i = 1 to j q = max(q,p[i]+r[j-1]) r[j] = q return r[n] 贪心算法(greedy algorithm) 通过局部最优的选择，能产生全局的最优选择。 找零钱问题 活动选择、区间覆盖、任务调度、教师排课,选出最大的互相兼容的活动集合 每次都选择活动结束时间最早的活动 分数背包问题 贪心算法不能解决，得用动态规划 0-1背包问题 1.容量固定，计算能装进背包的物品组合的最大重量 2.容量固定，计算能装进背包的物品组合的最大价值 霍夫曼编码（Huffman Coding） 广泛用于数据压缩中，其压缩率通常在 20%～90% 之间 霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率， 根据频率的不同，选择不同长度的编码。 对于等长的编码来说，我们解压缩起来很简单。但不等长的编码解压缩就比较麻烦 为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。 Prim 和 Kruskal 最小生成树算法 Dijkstra最短路径 问题： 贪心算法并不一定能得到最优解 计算几何 点和线段 线段和线段 点和多边形 碰撞检测 数学 数论 字符串 单模式串匹配算法 概念：主串，长度n 模式串，长度m BF算法(Brute Force) 中文叫作暴力匹配算法，也叫朴素匹配算法 拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。 理论上最坏情况时间复杂度是 O(n*m),但，大部分情况下，算法执行效率要比这个高很多 RK算法(Rabin-Karp算法) RK算法是借助哈希算法对BF算法进行改造，即对每个子串分别求哈希值，然后拿子串的 哈希值与模式串的哈希值比较，减少了比较的时间。 理想情况下，RK算法的时间复杂度是 O(n) 不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。 BM(Boyer-Moore)算法 它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的3到4倍 在实际的软件开发中，特别是一些文本编辑器中,应用比较多 核心思想： 利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位， 以此来减少不必要的字符比较，提高匹配的效率 坏字符规则（bad character rule） 好后缀规则（good suffix shift） 好后缀规则可以独立于坏字符规则使用。 因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。 KMP KMP算法跟BM算法的本质是一样的在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规 律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。 适用于：字符集比较小的情况 int match ( char* P, char* T ) { int* next = buildNext ( P ); int n = ( int ) strlen ( T ), i = 0; //文本串指针 int m = ( int ) strlen ( P ), j = 0; //模式串指针 while ( j < m && i < n ) //自左向右逐个比对字符 { if ( 0 > j || T[i] == P[j] ) //若匹配，或P已移出最左侧（两个判断的次序不可交换） { i ++; j ++; } //则转到下一字符 else j = next[j]; //模式串右移（注意：文本串不用回退） } delete [] next; //释放next表 return i - j; } int* buildNext ( char* P ) { size_t m = strlen ( P ), j = 0; //“主”串指针 int* N = new int[m]; //next表 int t = N[0] = -1; //模式串指针 while ( j < m - 1 ) { if ( 0 > t || P[j] == P[t] ) { //匹配 j ++; t ++; N[j] = t; //此句可改进... } else //失配 t = N[t]; } return N; } 多模式串匹配算法 字符串前缀查找 见：Trie数 AC自动机 该算法通过有限自动机巧妙地将字符比较转化为状态转移，此算法的时间复杂度与关键字的数目无关， 只跟文本长度有关，其时间复杂度为O(n) AC 自动机实际上就是在 Trie 树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了 AC自动机的构建 1.将多个模式串构建成Trie树； 2.在Trie树上构建失败指针（相当于 KMP 中的失效函数next数组）。 图形学 光照模型 视频 音频 网络 网络路由 推荐算法 相似性的判断 用欧几里得距离是用来计算两个向量之间的距离的。 分布式算法 Chord 协议 Kademlia(Kad)协议 概率算法 朴素贝叶斯算法 密码学 随机算法 对称加密 非对称加密(公钥加密) 单向散列函数 安全加密：hash(密码+salt) 唯一标识 数据校验 散列函数 负载均衡 数据分片 分布式存储 消息认证码 数字签名 机器学习 神经网络 多线程算法 操作系统 线程调度 内存分配 缓存淘汰 先进先出策略 FIFO(First In，FirstOut) 最少使用策略 LFU(Least Frequently Used) 最近最少使用策略 LRU(LeastRecently Used) 链表法 可以用链表保存，头存放最新的，尾放最旧的，每次有数据来时再动态调整位置。复杂度是O(n) 链表 + 散列表法 通过散列表和双向链表的组合使用，可以实现了一个高效的、支持 LRU缓存淘汰算法的缓存系统原型。 其中查找、删除和添加都可以在O(1)的时间完成 编程语言方面 垃圾回收算法 标记清除算法(python) 在一个有限图上进行遍历，遍历后分可达和不可达，不可达的会被清理 分代收集算法(一个优化手段) 为了防止垃圾回收启动太频繁，造成程序性能低下，把要处理的对象分成几代， 刚刚创立的对象是第 0 代；经过一次垃圾回收后，依然存在的对象，便会依次从上一代挪到下一代， 而每一代启动自动垃圾回收的阈值是可以单独指定的。当垃圾回收器中新增对象减去删 除对象达到相应的阈值时，就会对这一代对象启动垃圾回收。 数据结构 逻辑结构 集合、线性、树形、图结构 存储结构 顺序存储、链式存储、索引存储、散列存储 位图 from typing import Optional class Bitmap: def __init__(self, num_bits: int): self._num_bits = num_bits self._bytes = bytearray(num_bits // 8 + 1) def setbit(self, k: int) -> None: if k > self._num_bits or k < 1: return # byteIndex = k // 8 # bitIndex = k % 18 self._bytes[k // 8] |= (1 << k % 8) def getbit(self, k: int) -> Optional[bool]: if k > self._num_bits or k < 1: return return self._bytes[k // 8] & (1 << k % 8) != 0 if __name__ == "__main__": bitmap = Bitmap(10) bitmap.setbit(1) bitmap.setbit(3) bitmap.setbit(6) bitmap.setbit(7) bitmap.setbit(8) for i in range(1, 11): print(bitmap.getbit(i)) 线性表 顺序表(动态数组) 可根据大小动态扩容 链表 单链表 单链表反转： typedef struct list{ int item; struct list *next; }List; List* reverse(List* head) { if (head == NULL || head->next == NULL) return head; List* curr = head; List* next = head -> next; head->next = NULL; //首指向空 while (next) { List *next2 = next->next; next->next = curr; curr = next; next = next2; } return curr; } 删除、插入节点： 删除某个节点需要遍历才能知道其前驱节点，故：遍历+删除 O(n) + O(1) 从链表中删除一个数据的两种情况： 1.删除结点中“值等于某个给定值”的结点，此时链表需要遍历才能找到。 2.删除给定指针指向的结点，单链表此时就有劣势了。 双向链表 实际中一般都使用双向链表 删除、插入节点： 因知道其前驱节点，故：删除 O(1) 循环链表 优势：从链尾到链头比较方便 约瑟夫问题 N个人围成一圈，从第一个人开始报数，数到M的人出圈； 再由下一个人重新开始报数，数到M的人出圈 跳表(Skip list) 有序链表加多级索引的结构，就是跳表. Redis 中的有序集合(Sorted Set)就是用跳表来实现的 跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。 跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。 难点：跳表索引动态更新，在加节点和删除节点的同时更新索引 栈 栈既可以用数组来实现(叫作顺序栈)，也可以用链表来实现(叫作链式栈) 支持动态扩容的栈，只需底层依赖一个支持动态扩容的数组就可以了 当栈满了之后，就申请一个更大的数组，将原来的数据搬移到新数组中 应用场景: * 函数调用栈 * 表达式求值,34+13*9+44-12/3 (使用两个栈，一个保存操作数，另一个是保存运算符) * 括号匹配 * 浏览器前进、后退功能(需要两个栈，一个放访问过的，一个是放回退时push的，用于保留前进的页面) 队列 单向队列 双向队列 循环队列 阻塞队列 在队列基础上增加了阻塞操作，队列为空取阻塞，队列满插入阻塞 并发队列 线程安全的队列我们叫作并发队列，最简单的是直接在enqueue()、dequeue()上加锁 堆(最小堆、最大堆) (二叉)堆是一个数组，它可以被看成一个完全二叉树，除底层该树是完全充满的。 完全二叉树比较适合用数组来存储 最大堆满足：A[parent(i)] >= A[i] 父节点大于等于子节点 max_heapify 时间复杂度：O(log(n))跟高度一样 i为使最大堆性质失效的节点，通过让A[i]的值在堆中逐级下降，从而维护最大堆性质 最坏情况为失效的点在树的顶端 max_heapify(A,i) l = left(i) r = right(i) //选出A[i],A[left(i)],A[right(i)],并将其存在largest(最大值的索引)中 if l <= A.heap_size and A[l] > A[i] largest = l else largest = i if r <= A.heap_size and A[r] > A[largest] largest = r if largest != i exchange(A[i], A[largest]) max_heapify(A, largest) //递归的过程 build_max_heap(A) //常量级时间 O(n) A.heap_size = A.length for i = floor(A.length/2) downto 1 //对于完全二叉树来说，下标从A.length/2到n的节点都是**叶子节点** max_heapify(A,i) 插入： 一般插入到最后，然后从下往上的堆化 删除： 如果删除堆顶的节点，把尾部的节点移到堆顶然后再堆化 应用： 堆排序：最大堆 优先队列：最小堆常用于构建优先队列 数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队 往优先级队列中插入一个元素，就相当于往堆中插入一个元素； 从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素 1. 合并有序小文件 2. 高性能定时器 利用堆求 Top K 静态数据 维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。 大-->删除堆顶，并插入新数据 小-->不处理 动态数据 一直都维护一个 K 大小的小顶堆，当新来了数据后与堆顶元素比较 大-->删除堆顶，并插入新数据 小-->不处理 利用堆求中位数、前百分比的数据 可以利用两个堆，大顶堆(放小数据)、小顶堆(放大数据)，每次来数据了1.判断放那个堆中 2.维护两个堆的比例 实现其他算法的基础： 赫夫曼编码、图的最短路径、最小生成树算法等等 问题： 一个包含10亿个搜索关键词的日志文件，如何能快速获取Top10的搜索关键词？ 1.将10亿的数据用hash分片成10个文件 2.扫描文件生成key->num的散列表 3.生成一个大小为10的小顶堆 4.再比较这10个堆求top10 散列表(hash表) 散列函数+散列冲突解决 散列函数 1.不能太复杂，以免影响性能 2.生成的值要尽可能随机并且均匀分布 散列冲突解决 开放寻址法(open addressing) 线性探测方法(Linear Probing) 线性探测每次探测的步长是 1 二次探测(Quadratic probing) 探测探测的步长就变成了原来的“二次方” 双重散列(Double hashing) 先用第一个散列函数，若冲突，再用第二个散列函数 链表法(chaining) 装载因子 装载因子 = 填入表中的元素个数 / 散列表的长度 装载因子过大、过小怎么办？ 动态扩容(1.重新申请内存空间 2.重新计算哈希位置 3.并且搬移数据)、动态缩容 如何避免低效地扩容？ 1.达到阈值时申请空间 2.插入新数据时插到新空间，并把一部分旧数据搬移到新空间直到旧空间中的搬完 3.查找时先从新散列表中查找，如果没有找到，再去老的散列表中查找。 散列表碰撞攻击：精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里 散列表的查找缺点： 不能进行范围区间查找 树 数的表示 于指针的的链式存储法 基于数组的顺序存储法 树 表示法 带双亲的孩子链表法 左孩子右兄弟发表示为二叉树 二叉树(简洁，结构规范，描述能力强) 统计节点数 递推公式：count(tree) = 1 + count(tree.left) + count(tree.right) 递归基：count(NULL) = 0 int count(Tree tree) { if(tree == NULL) { return 0; } else { return 1 + count(tree.left) + count(tree.right); } } 获取树的高度 递归法，height(Tree) = 1 + max(height(Tree.left)，height(Tree.right)) 树的遍历 根前序：根->左->右 print可以替换成visit preOrder(r) = print r + preOrder(r->left) + preOrder(r->right) 根中序：左->根->右 inOrder(r) = inOrder(r->left) + print r + inOrder(r->right) 根后序：左->右->根 postOrder(r) = postOrder(r->left) + postOrder(r->right) + print r 应用： 逆波兰式(后缀表达式) a + b * c => 转变 => 象语法树 => 后序遍历树 => abc+* 计算值的过程：0.需要一个栈 1.遇到数字压栈 2.遇到算符从栈中弹出俩数字进行计算并压栈 前序非递归： def preorder(root): stack = [] stack.append(root) while stack: node = stack.pop() print node.val if node.right: //注意顺序 stack.append(node.right) if node.left: stack.append(node.left) def preorder(root): //使用回溯策略，每次左子树遍历完之后才回溯，然后遍历右子树 stack = [] while root or stack: if root: print root.val stack.append(root) # push root root = root.left # visit left else: root = stack.pop() # backtrack parent node root = root.right # visit right 中序非递归： def inorder(root): stack = [] while root or stack: if root: stack.append(root) root = root.left else: root = stack.pop() print root.val #跟先序的区别在于：打印的回溯时间点不同 root = root.right 后序非递归： def postorder(root): stack1 = [] stack2 = [] stack1.append(root) while stack1: node = stack1.pop() stack2.append(node.val) if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) while stack2: print(stack2.pop()) 二叉查找树 左子树中的节点比自己小，右子树中的节点比自己大 支持快速查找、插入、删除操作 删除： 情况1：删除的节点没有子节点，直接删除 情况2：要删除的节点只有一个子节点(只有左子节点或者右子节点)，更新子节点的父节点为删除节点的父节点 情况3：删除的节点有两个子节点，找到这个节点的右子树中的最小节点，把它替换到要删除的节点上 取巧的方法：标记删除而不真正的删除 支持重复数据的二叉查找树 方法1.相同的key通过链表或动态数组存 方法2.每个节点仍然只存储一个数据，若碰到相同的就将这个要插入的数据放到这个节点的右子树 优势： 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，比起散列表来要高效的多 劣势： 极度不平衡的二叉查找树再插入删除会退化成链表，高度不是logn而是n。解决：平衡二叉树 判定树和哈夫曼树 哈夫曼算法、哈夫曼编码 红黑树 平衡二叉树严格定义：二叉树中任意一个节点的左右子树的高度相差不能大于1， 但一般也不用严格遵循，只要树的高度不比log(n)大很多就行 平衡树的一种，也是二叉搜索树，但节点多了一个color属性 定义： 1.每个节点或是红色，或是黑色 2.根节点是黑色的； 3.每个叶子节点都是黑色的空节点(NIL) 目的：为了简化红黑树的代码实现而设置的 4.任何上下相邻的节点都不能同时为红色 5.每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点； 实现效果： 高度最高不超过2log(n) 推论： 1.去除红色节点-->变成全黑的四叉树-->从四叉树中取出某些节点，放到叶节点位置变成完全二叉树，高度为log(n) 2.红色比黑色小，红色高度也小于log(n) 红黑树的平衡过程 红黑树的插入、删除操作会破坏红黑树的定义 方法：就像将打乱的魔方还原好一样，遇到什么样的节点排布，就用对应的公式去调整 调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点 会随着不停地迭代处理，而不断发生变化 最开始的关注节点就是新插入的节点，要注意当前的关注点是哪一个才能对应到具体的哪一种情况 调整的过程包含两种基础的操作：左右旋转和改变颜色 插入(插入的节点必须是红色的)： case1、case2、case3 删除： 1.针对删除节点初步调整，使其满足定义5 case1、case2、case3 2.针对关注节点进行二次调整，使其满足定义4 case1、case2、case3、case4 AVL树 最先发明的高度平衡的二叉树，查找的效率非常高 为了维持这种高度的平衡，插入、删除的消耗比红黑树大 B树 B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据； B 树中的叶子节点并不需要链表来串联。 Trie树(也叫“字典树”) 比较适合的是查找前缀匹配的字符串 本质是利用字符串之间的公共前缀，将重复的前缀合并在一起 Trie还应用在自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等 如果用来构建 Trie 树的这一组字符串中，前缀重复的情况不是很多，那 Trie 树这种数 据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。 对数据集的要求 字符串的字符集不能太大 前缀重合比较多 构造Trie树 结构 class TrieNode { char data; TrieNode children[26]; //当然也可以换成有序数组、跳表、散列表、红黑树等 } 在Trie树中查询一个字符串 时间复杂度是 O(k)，k表示要匹配的字符串的长度。 查找前缀匹配的字符串 在从trie树根节点查找输入的单词，当达到最后一个字符后，以最后一个字符为根节点的子树便为匹配的字符串， 此时需要遍历这棵树，然后去除所有的_is_ending_char = true的节点 class TrieNode: def __init__(self, data: str): self._data = data self._children = [None] * 26 self._is_ending_char = False class Trie: def __init__(self): self._root = TrieNode("/") def insert(self, text: str) -> None: node = self._root for index, char in map(lambda x: (ord(x) - ord("a"), x), text): if not node._children[index]: node._children[index] = TrieNode(char) node = node._children[index] node._is_ending_char = True def find(self, pattern: str) -> bool: node = self._root for index in map(lambda x: ord(x) - ord("a"), pattern): if not node._children[index]: return False node = node._children[index] return node._is_ending_char # 如果是false，则不能完全匹配，只是前缀 if __name__ == "__main__": strs = ["how", "hi", "her", "hello", "so", "see"] trie = Trie() for s in strs: trie.insert(s) for s in strs: print(trie.find(s)) print(trie.find("swift")) 数和森林 数转成二叉树 森林转换成二叉树 二叉树转换成森林 图 概念：顶点、边、度(degree)、入度、入度、无向图、有向图、带权图 表示方法： 邻接矩阵 底层依赖一个二维数组 缺点：对于无向图或稀疏图来说比较浪费空间 优点：查询效率高、而且方便矩阵运算 邻接表 每个顶点都对应一个链表，存储与其相连接的其他顶点 缺点：查找比较麻烦，但可以将节点的链表换成其他的，比如红黑树、有序动态数组、跳表等 图的遍历 广度搜索（BFS Breadth-First-Search） def print_path(prev, s, t): if prev[t] != None and t != s: print_path(prev, s, prev[t]) #假设其已经完成了打印 print(t + " ") def bfs(graph, s, t): s:start t:target if s == t: return prev = [None] * graph._num_vertices visited = [False] * graph._num_vertices visited[s] = True q = deque() q.append(s) while q: v = q.popleft() for neighbour in self._adjacency[v]: if not visited[neighbour]: prev[neighbour] = v if neighbour == t: print_path(prev, s, t) return visited[neighbour] = True q.append(neighbour) 深度搜索（DFS） 深度优先搜索用的是一种比较著名的算法思想，回溯思想 def dfs(graph, s, t): found = False visited = [False] * graph._num_vertices prev = [None] * graph._num_vertices def _dfs(from_vertex): nonlocal found if found: return visited[from_vertex] = True if from_vertex == t: found = True return for neighbour in graph._adjacency[from_vertex]: if not visited[neighbour]: prev[neighbour] = from_vertex _dfs(neighbour) _dfs(s) print_path(prev, s, t) 最短路径 最短路径的最优子结构：最短路径的子路径也是最短路径 Dijkstra 带权重的(非负)有向图上单源最短路径算法 G:G = (V,E) s:start init_single_source(G,s) for v in G.V v.d = ∞ //距离 v.pre = null s.d = 0 relax(u,v,w) //从u到v是否更优，w是权重表， if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.pre = u dijkstra(G,w,s) init_single_source(G,s) Q = G.V //最小优先队列，以距离为准 while Q u = extract_min(Q) for v in Adj[u] relax(u,v,w) A*寻路算法 dijkstra只考虑了顶点与起点的路径长度的大小，来安排出队列顺序的 与起点越近的顶点，就会越早出队列。我们并没有考虑到这个顶点到终点的距离 A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm） f(i)的专业叫法叫做：估价函数（evaluation function） f(i)=g(i)+h(i) g：起点到当前点的距离 h：当前点到目标点的距离 最小生成树 Prim算法 Kruskal算法 拓扑排序 拓扑排序本身就是基于有向无环图(有环的话就死循环了)的一个算法 凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决 除此之外，拓扑排序还能检测图中环的存在。 对于Kahn 算法来说，如果最后输出出来的顶点个数，少于图中顶点个数，图中还有入度不是0 的顶点，那就说明，图中存在环。 算法： 1.Kahn算法 2.DFS算法 索引 索引的需求定义 1.功能性需求 数据是格式化数据还是非格式化数据？ 数据是格式化数据还是非格式化数据？ 索引存储在内存还是硬盘？ 索引存储在内存还是硬盘？ 单关键词查找还是多关键词组合查找？ 2.非功能性需求 不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。 在考虑索引查询效率的同时，我们还要考虑索引的维护成本。 构建索引常用的数据结构有哪些？ 红黑树 B+ 树 跳表 布隆过滤器