宜宾网站建设哪家好,关于进一步加强门户网站建设,软文营销代理,做外贸哪个网站要办信用卡的《算法之道》精华 经典算法部分 本书作者邹恒明#xff0c;作者另有一本书《数据结构之弦》#xff0c;以及《操作系统之哲学原理》都是非常好的书这本书能够算得上是深入浅出#xff0c;文笔非常好。作者加入了非常多自己的思考本文包含经典算法部分第十章 排序与次序 插入… 《算法之道》精华 经典算法部分 本书作者邹恒明作者另有一本书《数据结构之弦》以及《操作系统之哲学原理》都是非常好的书这本书能够算得上是深入浅出文笔非常好。作者加入了非常多自己的思考本文包含经典算法部分第十章 排序与次序 插入排序 从无序部分抽取一张插入有序部分为原地排序。无需占用暂时存储空间最优情况下为O(n)。平均O(n^2)折半插入排序 插入时使用二分查找归并排序 分治从中间分解分别排序后进行细致的合并异地排序须要占用额外空间n30时性能比插入排序更好。复杂度固定为O(nlog(n))快排 分治复杂的部分在于分解。而归并复杂在于合并原地排序最坏情况为O(n^2)但仅仅要不是每次都是最坏复杂度就不是n^2具有韧性不论什么基于比較的排序决策树高度至少为nlog(n)计数排序 元素值范围必须有限空间复杂度高O(n)基数排序 从最低位到最高位排序每一位排序都採用稳定排序如计数排序一位排序应该选择log(n)个比特。使总体成本最低桶排序 把n元素按值分到n个桶里每一个桶内部进行插入排序。将各桶首位相连元素应该是均匀分布高速次序选择求第K大的数 使用快排的partition最差O(n^2)。平均O(n)线性最差高速次序选择 将元素每5个一组。分别取中值。在n/5个中值里面找到中值作为partition的pivot为什么*不每3个一组保证pivot左边右边至少3n/10个元素最差O(n)第十一章 搜索与散列 顺序搜索 在序列里面假设搜索频率从头到尾指数递减。则为O(1)折半搜索 对于有序序列为O(logn)常数搜索散列搜索 直接散列很easy不会发生碰撞空间浪费大除法模除法散列 元素对散列表大小m取模得到m必须为素数否则造成不均匀散射。比方m包括因子d而大部分元素对d余数相等m不能靠近2的幂。如m为2的幂散列结果将不依赖元素的全部位。靠近也不行为什么乘法散列 h(k) (A * k ) % 2^r (w - r)。w为计算机字宽A为2^(w-1)与2^w之间的一个奇数乘方取中法乘方n次常取n2取中间r位开放寻址散列散列碰撞时纵深扩展加入一个链表 平均搜索时间为O(1a)a为载入因子封闭寻址散列散列碰撞时为元素找到还有一个位置 找还有一个位置的操作称为探寻线性探寻 h(k,i) (h(k) i) % mh(k)为家位向单方向寻找未被占用的位置易出现顶级聚集非线性探寻 平方探寻 h(k,i) (h(k) c1 * i c2 * i^2) % m 易出现次级聚集双重散列探寻 使用两个散列函数h1、h2来构造新散列函数h(k,i) (h1(k) i * h2(k) ) mod m伪随机探寻 使用伪随机序列存在次级聚集不成功搜索的探寻次数期望为1/(1-a)成功搜索探寻次数最多为1 / a * ln( 1/(1-a))封闭散列不能删除元素。能够放标记解决。假设插入相比搜索很稀疏则能够通过又一次散列解决空位问题随机化散列 找到一组散列函数。每次随机选择一个不同的散列函数用于避免单个散列函数极端情况下聚集效应严重全域散列 一组H个散列函数将随意两个不同的元素映射到同一位置的函数个数为H/m完美散列 n个元素。构造mO(n)大小的散列表使搜索最坏达到O(1)採用双层散列第一层大小n第二层每一个表的大小为落到第一层位置i上的元素个数的平方空间消耗为O(n)第十二章 最短路径 假设图中有负环则不存在最短路径单源多点最短路径 Dijkstra算法 贪婪算法。要求不存在负路径最优子结构最短路径里的每一段都是两点之间的最短路径贪婪选择属性路径向外延伸的下一个节点就是离源点近期的节点每次选取离源点近期的节点更新全部与此节点相邻节点的距离时间复杂度为O(V^2)。採用堆实现。能够达到O(E log(V))。与Prim算法同样Bellman-Ford算法 能够应对负权重进行V-1轮降距每次更新图中全部边复杂度为O(VE)BFS 各边权重相等的情况O(VE)多源多点最短路径 Floyd-Warshall算法 动态规划算法子问题为从i到j中间结点仅仅属于集合1...k的最短路径长度c_ijk min{c_ij(k-1), c_ik(k-1) ckj(k-1)}|k复杂度O(n^3)Jonhson算法 等效变换为无负权重的图使用Dijkstra算法加入一个节点s到全部点路径长度为0执行Bellman-Ford算法对节点赋值对每一个节点执行Dijkstra算法复杂度主要是Dijkstra算法运算为O(VE V^2 log(V))若Bellman-Ford算法报告有负环存在不能使用此方法 转载请注明作者Focustc博客地址为http://blog.csdn.net/caozhk原文链接为点击打开 转载于:https://www.cnblogs.com/gavanwanggw/p/7259274.html
