佛山营销网站设计,绍兴建设局网站,已有备案号新增网站备案要关闭原先的站点吗,进入淘宝网官网首页 淘宝总结#xff0c;建议看EXCEL的《算法》页签#xff0c;不然感觉有点乱 备注原理/步骤时间复杂度空间复杂度串的应用模式匹配简单/暴力O(mn) KMP O(mn) 树的应用树哈夫曼树1、带权路径长度WPL 2、外部排序-最佳归并树1、哈夫曼树的度#xff0c;只有0和m#xff08;m叉… 总结建议看EXCEL的《算法》页签不然感觉有点乱 备注原理/步骤时间复杂度空间复杂度串的应用模式匹配简单/暴力O(mn) KMP O(mn) 树的应用树哈夫曼树1、带权路径长度WPL 2、外部排序-最佳归并树1、哈夫曼树的度只有0和mm叉树王道P176 2、哈夫曼编码是从根结点到叶子结点的路径上的01组合王道P180.T4 3、同一组编码/权值构造出来的哈夫曼树可以不同【自己举个例子就知道了】王道P180.T6A 4、路径长度指Σ(叶子结点的值 x 到根的长度数)之和【领悟哈夫曼树的构造除了第一次用m个数据如0、2、3其他每次只用m-1个数据因为有1个数据是来自下一层的和】王道.P359.T07 并查集1、Kruskal克鲁斯卡尔王道.P182.T102、无向图的连通性判断 图的存储邻接矩阵O( |V|2 ) 邻接表删除某个顶点相关的所有边 有向图O( |V| |E| )无向图O( |V| 2|E| ) 有向图O( |V| |E| ) 十字链表有向图顶点表[dataedge1edge2] 边表[弧尾点弧头点弧头指针弧尾指针info]O( |V| |E| ) 邻接多重表无向图顶点表[dataedge] 边表[点1点2指针1指针2info] O( |V| |E| ) 图的遍历BFS广度优先1、队列 2、相当于树的层次遍历像波纹一样推开遍历邻接矩阵O( |V|2 ) 邻接表O( |V| |E| )O( |V| ) DFS深度优先1、栈 2、相当于树的先序遍历3、可用于判断有向图是否有回路4、逆拓扑排序王道P210.T111、一条路走到黑 2、再退一步再走到黑图的应用I 最小生成树1、权值的和为最小 2、没有权值相同的边生成树的树形才唯一3、最小生成树的代价一定是唯一的王道P228.T18Prim普利姆只与点有关贪心算法1、n个结点时间复杂度与边无关因为是选n-1边没选到的边,再多也无用适合稠密图 2、n个结点1个最小的其余n-1个相等的值从不同的顶点开始Prim算法则会得到n-1种不同的最小生成树王道.P228.T18.III1、一个顶点选连接的最小的边最小边将已经连接的点作为整体看与未连接的边的权重/值最小的一个选完若构成环则去掉刚选的边退到上一个顶点 2、结束所有顶点都连接时O( |V|2 ) 普克扑克Kruskal克鲁斯卡尔只与边有关贪心算法适合边稀疏1、所有边从小到大排序依次选择若构成环去掉继续选下一个 2、结束所有顶点都连接时 O( nlog2n )n是边 II 最短路径简单路径BFS广度优先1、无权单源点到点 2、只能无向图权值为1或相同/邻接矩阵O( |V|2 ) 邻接表O( |V| |E| ) 广迪弗甘道夫Dijkstra迪杰斯特拉贪心算法1、带权单源点到点 2、负权值、负回路不适用1、主要3个元素标记、距离、前驱 2、选一个点先初始化 3、①选中距离最小且未标记的点标记置为True②更新由点到其他未标记的距离、前驱 4、结束所有结点标记都为TrueO( |V|2 ) Floyd弗洛伊德1、带权所有顶点 2、负回路不适用1、A[i][j] A[i][*] A[*][j]选择一个点*作为转中点到其他点的距离更新 2、每次选择都需要更新邻接矩阵O( |V|3 )O( |V|2 ) III 有向无环图描述表达式DAGDirected Acyclic Graph 最底层的元素都只有一个1、先按顺序写出所有的字母作为最底层的元素 2、依次往上连接符号表示一个小的运算 IV 拓扑排序AOVActivity On Vertex Network1、有拓扑序列就不存在回路 ∵要选入度为0回路是环不存在入度为0的结点 2、每个顶点出现仅有一次 3、可能排序不唯一 4、A排在B前面则不存在 B —A 的路径依次选择入度为0的点 逆拓扑排序·DFS深度优先出栈时读出DFS可得逆拓扑顶点有序序列依次选择出度为0的点 V 关键路径AOEActivity On Edge Network 1、缩短所有关键路径上共有的任意一个关键活动的时间才可以缩短关键路径长度 2、 e(i)事件最早发生时间 l(i)事件最迟发生时间 ae(i)活动最早发生时间 al(i)活动最迟发生时间 dae(i)-al(i)为0就是关键活动从起点到结束点长度最大的路径 平均查找长度 ASL类似EX数学期望查找线性结构顺序查找1、数组、链表均可 2、每个元素查找成功的比较次数只与位置有关与是否有序无关王道.P253.T2O(n)一般ASL成功 ΣPi(n-i1) 等概率 ASL成功 (n1)/2 ASL不成功 n1王道.P250推导 折半查找二分查找1、必须有序且只能用顺序存储数组 2、平衡二叉树 3、(lowhigh)/2 结果向上取整或向下取整但一棵树只能二选一王道.P254.T12/T21查找O(log2n) 插入删除O(n)等概率ASL成功 ≈log2(n1)-1王道P252例子 P254T13/T18 分块查找1、块内随意块间有序折半查找索引表顺序查找块内表 2、索引表一个块的最大的关键字和第一个元素的位置 3、最理想的块长√n且平均查找长度为 (√n) 11、先查索引表顺序查找/(数组时)二分查找 2、块内顺序查找 (b1)/2 (s1)/2分为 b 块每块有 s 个记录王道.P254.T16 树形结构二叉排序树BST - 二叉查找树 - 左 根 右0、空树也是二叉排序树 1、可以形成单支树查找长度为 n时间复杂度是O(nlogn) 2、中序遍历会得到一个递增的序列 3、 叶结点删除后插入与原树一定相同 非叶结点删除后插入与原树一定不同 王道.P276.T21左子树结点的值 根结点的值 右子树结点的值查找O(log2n)/O(n) 插入删除O(log2n)平衡二叉树AVL - 发明者G. M. Adelson-Velsky和E. M. Landis - 是特殊的二叉排序树0、 - 空树也是平衡二叉树 - 平衡因子左子树高度-右子树高度 - LL、RR、LR、RL 4种破坏平衡的方式 1、左右子树高度差不超过1 2、不一定是完全二叉树 3、 n00n11n22 nh nh-1 nh-2 1 构造最大高度 h 的平衡二叉树所需的最少的结点数nh王道.P275.T10/T11此时非叶结点的平衡因子为1王道.P276.T20 4、平衡二叉树叶结点/非叶子结点删除后插入与原树可能相同也可能不同王道.P276.T25 O(log2n) O(log2n) B树多路平衡查找树 1、B树只支持随机查找B树支持顺序查找、随机查找∵B树的叶子结点包含全部关键字信息∴支持顺序 2、1、每个结点 [(m/2)向上取整]-1 ≤ 关键字 ≤ m-1王道.P290.T01 2、平衡因子0绝对平衡所有叶子结点都在同一层 3、高度 h m 阶B树王道.P291.T06 ①结点数最少2h - 1满二叉树 ②结点数最多mh - 1满m叉树 4、外部结点不算层数 5、m阶n个点最大高度、最小高度 P287王道.P291.T08/T09 B树1、用于各种索引文件索引、数据库索引 散列表哈希表 散列函数哈希函数1、适合关键字集合与地址集合之间存在对应关系 2、平均查找长度ALS - 与表长、元素都无关 - 与散列函数、处理冲突的方法、装填因子有关3、装填因子α 已有记录数/表长度 α越大 - 表示哈希表的装满的程度 - 越容易发生冲突王道.P302.T06 ∴想要提高查找效率需要减小装填因子 4、探测插入前检测次数王道.P302.T07处理冲突的方法1开放地址法Hi [ H(key) di ] % m删除时只能是假删除否则影响查找I 线性探测法1、映射后一直探测到下一个可以存放的地址 2、会出现元素堆积/聚集同义词与非同义词发生冲突都可以造成堆积大大降低查询效率 3、细节空的也会消耗1次对比的机会王道.P303.T17/T18di 0 1 2 3 … m-1理想情况O(1) II 平方探测法1、m 是一个 4k3 的质数 2、有效避免堆积di 02 12 -12 22 -22 … k2 -k2 III 伪随机序列法di 一个随机数列可以自己定义 IV 双散列法再散列法再哈希法kHash1(key) dHash2(key) 探测顺序(kd)%n、(k2d)%n、(k3d)%n…处理冲突的方法2拉链法链接法链接地址法1、不会发生堆积数组下标作为指针的起始用链表存数据 稳定性排序插入排序直接插入1、不考虑哨兵的比较 - 最坏的情况需要 n(n-1)/2 次比较 - 最好的情况只要 n-1 次比较有序第一个元素视为已经排好序的后面每个元素都只要比较1次所以只要n-1次比较1、第1个元素视为有序无序消耗比较次数 2、第i个元素前面都是有序的 3、从后往前找插入位置然后进行插入最好初始化序列原本有序O(n)平均O(n2/4)所以是O(n2)和最坏一样 最坏初始化序列刚好逆序O(n2)O(1)每次只要常数个辅助单元Y先比较再移动 - 不稳定4个希尔选择快速堆选的太快不稳定 - 不能原地工作的3个内部排序基数O(max(r))、快速O(log2n)、归并O(n)【鸡块饼占空间】 - 原地工作空间复杂度O(1) https://www.cnblogs.com/Xieyang-blog/p/8340578.htmlB34 1、时间复杂度比较移动与序列初始状态无关 - 选择排序 - 堆排序 - 归并排序 - 基数排序 口诀一堆乌龟选基友和初始状态无关 2、排序趟数和原始状态有关2个交换排序都有关冒泡 快速 3、利用顺序存储的随机访问特性采用链式会降低速度 - 希尔排序 - 堆排序 折半插入二分插入数组因为是在有序表中查找插入位置所以查找可以先采用二分查找再移动元素O(n2)O(1)Y 希尔排序缩小增量排序数组不适用于链表1、%d 的为一组d间隔1王道.P316.T08然后使用直接插入排序同组元素 2、d减小再进行排序最好/平均O(n1.3)最坏O(n2)O(1)N相同元素在不同组时可能发生位置变化交换排序两两比较次序相反的就交换直到所有数据没有反序为止冒泡排序起泡排序 - 最坏的情况刚好逆序比较和交换次数相同都需要 n(n-1)/2 次 - 适用于数组、链表 - 在一趟排序过程中没有发生交换则算法可以提前结束1、每次都是从头到尾两两比较满足条件的两两交换 2、细节每次冒泡就确定了本趟“最后元素”的位置剩余趟数就不用消耗比较次数王道.P323.T08最好有序O(n) 最坏/平均逆序O(n2)O(1)Y 快速排序递归排序1、待排序列最适合采用顺序存储40811T10 2、有序快排最慢原则有序每次划分是 0 和 n-1 个元素 每次将表分为长度相近的两个子表时最快王道.P323.T9 3、递归次数/趟数 - 对尚未确定最终位置的所有元素进行一遍处理。如第二趟需要都处理左右两个子块才算一趟王道.P324.T17 - 与初始数据的排列次序有关有序最慢原则 - 与划分后的分区处理前后顺序无关408.10T104、每一趟排序后基准值元素会放在最终的位置选一个基准值用两个前后两个指针 i、j 1、比基准值大将元素放在j然后jj-1 2、比基准值小将元素放在i然后ii1 3、与基准值相等不处理 ij时左右继续重复上述操作递归最好/平均O(nlog2n)最平衡的划分每次划分左右元素个数差不多都是n/2最坏O(n2)有序元素递归工作栈需要空间 最小O(log2n) 最大O(n)N同右侧的相同元素都小于基准值都要移去左边那么这2个相同的元素相对位置会改变选择排序在所有记录中每次选择最小的放在最后/前面选择排序1、数组、链表均可 2、比较次数与初始状态无关n个元素都需要 n-1 趟1、每次都要遍历排好序之后的待排序列2、选择最小的数与无序的第一个数交换比较次数O(n2)2层for循环移动次数O(n)O(1) N 堆排序1、在1亿个数里面找出100个最小值用大根堆根 ≥ 左、右 2、堆是用来排序的其查找效率不高 3、堆必须是一个完全二叉树1、破坏堆取出根值并用完全二叉树的最后一个元素填充根值 2、恢复堆插入/删除O(log2n) 构建堆O(n) 排序O(nlog2n)O(1)N 胜者树 - 竞赛树排序 - 其实就是败者树 O(nlog2n) 归并排序归并排序1、N个元素k路归并趟数mkm N 2、m [logkN]向上取整趟数2路归并 2个元素/2个块/2个小组进行1对1比大小合并成一组组成新的有序数列2路归并 O(nlog2n)每一趟是O(n)一共 log2n 趟O(n)合并需要n个辅助单元Y基数排序分配收集排序基数排序适用于 1、n比较大 2、r比较小 3、方便拆且d比较小 不适用float、double的实数将n个元素每一个可以拆成d个关键字每一个关键字有自己的r基数范围O( d·(nr) )O(max(r))Y外部排序归并排序1、外部排序时间 读写外存的时间 内部排序所需时间 内部归并所需时间 2、优化思路减少读写外存的趟数多路归并可以减少趟数2路归并需要在内存分配2个输入缓冲区 4路归并需要在内存分配4个输入缓冲区 r个初始归并段做K路归并 3、内存中任意一个输入缓冲区空了需要立即从磁盘中加载一个块继续在内存中排序1、生成初始的归并段让内部有序每一块都需要读、写一次 2、归并2的次方个“归并段”优化1 败者树选择排序优化2 置换-选择排序 最佳归并树哈夫曼树1、置换-选择排序生成不确定但更长的初始归并段 实际是一个一个先放在CPU输出缓冲区当缓冲区满了才放回磁盘 2、最佳归并树/哈夫曼树 - 初始归并段的长度 每段中的整块数 - m路归并初始段有x个则需 (x-1)%(m-1) u ≠ 0时需要 m-1-u 个0的虚段 - 读写次数 2 · WPL
