销售网站平台怎么做的,浙里建官网登录,产品设计公司怎么接单,安徽企业年报网上申报入口# 数据结构基础
学习思路 避免孤立的学习知识点#xff0c;要关联学习。比如实际应用当中#xff0c;我们经常使用的是查找和排序操作#xff0c;这在我们的各种管理系统、数据库系统、操作系统等当中#xff0c;十分常用#xff0c;我们通过这个线索将知识点串联起来要关联学习。比如实际应用当中我们经常使用的是查找和排序操作这在我们的各种管理系统、数据库系统、操作系统等当中十分常用我们通过这个线索将知识点串联起来 数组的下标寻址十分迅速但计算机的内存是有限的故数组的长度也是有限的实际应用当中的数据往往十分庞大而且无序数组的查找最坏情况需要遍历整个数组后来人们提出了二分查找二分查找要求数组的构造一定有序二分法查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作比较复杂因此在一个增删查改比较频繁的数据结构中数组不会被优先考虑
普通链表由于它的结构特点被证明根本不适合进行查找
哈希表是数组和链表的折中同时它的设计依赖散列函数的设计数组不能无限长、链表也不适合查找所以也不适合大规模的查找
二叉查找树因为可能退化成链表同样不适合进行查找
AVL树是为了解决可能退化成链表问题但是AVL树的旋转过程非常麻烦因此插入和删除很慢也就是构建AVL树比较麻烦
红黑树是平衡二叉树和AVL树的折中因此是比较合适的。集合类中的Map、关联数组具有较高的查询效率它们的底层实现就是红黑树。
多路查找树 是大规模数据存储中实现索引查询这样一个实际背景下树节点存储的元素数量是有限的(如果元素数量非常多的话查找就退化成节点内部的线性查找了)这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁进而导致查询效率低下。
B树与自平衡二叉查找树不同B树适用于读写相对大的数据块的存储系统例如磁盘。它的应用是文件系统及部分非关系型数据库索引。
B树在B树基础上为叶子结点增加链表指针(B树叶子有序链表)所有关键字都在叶子结点 中出现非叶子结点作为叶子结点的索引B树总是到叶子结点才命中。通常用于关系型数据库(如Mysql)和操作系统的文件系统中。
B*树是B树的变体在B树的非根和非叶子结点再增加指向兄弟的指针, 在B树基础上为非叶子结点也增加链表指针将结点的最低利用率从1/2提高到2/3。
R树是用来做空间数据存储的树状数据结构。例如给地理位置矩形和多边形这类多维数据建立索引。
Trie树是自然语言处理中最常用的数据结构很多字符串处理任务都会用到。Trie树本身是一种有限状态自动机还有很多变体。什么模式匹配、正则表达式都与这有关。 A. 数据结构 知识点数据结构是基础中的基础任何进阶都逃不开这些知识点。 数据结构 - Overview B. 数据结构之 线性结构首先理解数据结构中线性结构及其延伸数组和矩阵链表栈和队列等。 线性表 - 数组和矩阵 数组是一种连续存储线性结构元素类型相同大小相等数组是多维的通过使用整型索引值来访问他们的元素数组尺寸不能改变线性表 - 链表 n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点每个节点只有一个后续节点首节点没有前驱节点尾节点没有后续节点。确定一个链表我们只需要头指针通过头指针就可以把整个链表都能推出来线性表(散列) - 哈希表 散列表Hash table也叫哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表。pdai线性表 - 栈和队列 数组和链表都是线性存储结构的基础栈和队列都是线性存储结构的应用 C. 数据结构之 逻辑结构树然后理解数据结构中逻辑结构之树二叉搜索树(BST)平衡二叉树(AVL)红黑树(R-B Tree)哈夫曼树前缀树(Trie)等。 树 - 基础和Overview 树在数据结构中至关重要这里展示树的整体知识体系结构和几种常见树类型树 - 二叉搜索树(BST) 本文主要介绍 二叉树中最基本的二叉查找树Binary Search Tree又二叉搜索树二叉排序树它或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。树 - 平衡二叉树(AVL) 平衡二叉树Balanced Binary Tree具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)F(n-1)F(n-2)1 这个类似于一个递归的数列可以参考Fibonacci数列1是根节点F(n-1)是左子树的节点数量F(n-2)是右子树的节点数量。树 - 红黑树(R-B Tree) 红黑树Red Black Tree 是一种自平衡二叉查找树是在计算机科学中用到的一种数据结构典型的用途是实现关联数组是平衡二叉树和AVL树的折中。树 - 哈夫曼树 哈夫曼又称最优二叉树, 是一种带权路径长度最短的二叉树。树 - 前缀树(Trie) Trie又称字典树、单词查找树或键树是一种树形结构是一种哈希树的变种。典型应用是用于统计排序和保存大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。它的优点是利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树高。 D. 数据结构之 逻辑结构图最后理解数据结构中逻辑结构之图图基础图的遍历最小生成树(Prim Kruskal)最短路径(Dijkstra Frolyd)拓扑排序(Topological sort)AOE 关键路径等。 图 - 基础和Overview 图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中图是最灵活的数据结构之一很多问题都可以使用图模型进行建模求解。例如: 生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。图 - 遍历(BFS DFS) 图的深度优先搜索(Depth First Search)和树的先序遍历比较类似; 广度优先搜索算法(Breadth First Search)又称为宽度优先搜索或横向优先搜索图 - 最小生成树(Prim Kruskal) Kruskal算法是从最小权重边着手将森林里的树逐渐合并prim算法是从顶点出发在根结点的基础上建起一棵树图 - 最短路径(Dijkstra Frolyd) 最短路径有着广泛的应用比如地图两点间距离计算公交查询系统路由选择等图 - 拓扑排序(Topological sort) 拓扑排序主要用来解决有向图中的依赖解析(dependency resolution)问题图 - AOE 关键路径 关键路径在项目管理计算工期等方面有广泛等应用提升工期就是所见缩减所有关键路径上的工期并且在实现时需要应用到之前拓扑排序的算法(前提: 有向无环图有依赖关系) # 排序算法详解 A. 常见排序概要重点理解几个排序之间的对比时间和空间复杂度以及应用。PS越简单越要提高认知效率做到战略上藐视战术上重视。 排序 - Overview B. 常见排序详解具体分析各种排序及其复杂度查漏补缺在综合复杂度及稳定性情况下通常希尔, 快排和 归并需要重点掌握。 排序 - 冒泡排序(Bubble Sort) 它是一种较简单的排序算法。它会遍历若干次要排序的数列每次遍历时它都会从前往后依次的比较相邻两个数的大小如果前者比后者大则交换它们的位置。这样一次遍历之后最大的元素就在数列的末尾 采用相同的方法再次遍历时第二大的元素就被排列在最大元素之前。重复此操作直到整个数列都有序为止排序 - 快速排序(Quick Sort) 它的基本思想是: 选择一个基准数通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。排序 - 插入排序(Insertion Sort) 直接插入排序(Straight Insertion Sort)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素无序表中包含有n-1个元素排序过程中每次从无序表中取出第一个元素将它插入到有序表中的适当位置使之成为新的有序表重复n-1次可完成排序过程。排序 - Shell排序(Shell Sort) 希尔排序实质上是一种分组插入方法。它的基本思想是: 对于n个待排序的数列取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列所有距离为gap的倍数的记录放在同一个组中然后对各组内的元素进行直接插入排序。 这一趟排序完成之后每一个组的元素都是有序的。然后减小gap的值并重复执行上述的分组和排序。重复这样的操作当gap1时整个数列就是有序的。排序 - 选择排序(Selection sort) 它的基本思想是: 首先在未排序的数列中找到最小(or最大)元素然后将其存放到数列的起始位置接着再从剩余未排序的元素中继续寻找最小(or最大)元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。排序 - 堆排序(Heap Sort) 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。排序 - 归并排序(Merge Sort) 将两个的有序数列合并成一个有序数列我们称之为归并。归并排序(Merge Sort)就是利用归并思想对数列进行排序。排序 - 桶排序(Bucket Sort) 桶排序(Bucket Sort)的原理很简单将数组分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序排序 - 基数排序(Radix Sort) 它的基本思想是: 将整数按位数切割成不同的数字然后按每个位数分别比较。具体做法是: 将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列 # 算法思想详解 A. 算法思想 详解紧接着我们通过理解算法背后常用的算法思想进行归纳总结并通过leetcode练习来辅助理解和提升。 算法思想 - 分治算法 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解算法思想 - 动态规划算法 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中可能会有许多可行解。每一个解都对应于一个值我们希望找到具有最优值的解。动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解算法思想 - 贪心算法 本文主要介绍算法中贪心算法的思想: 保证每次操作都是局部最优的并且最后得到的结果是全局最优的算法思想 - 二分法 本文主要介绍算法思想中分治算法重要的二分法比如二分查找二分查找也称折半查找Binary Search它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。算法思想 - 搜索算法 本文主要介绍算法中搜索算法的思想主要包含BFSDFS算法思想 - 回溯算法 Backtracking(回溯)属于 DFS, 本文主要介绍算法中Backtracking算法的思想。回溯算法实际上一个类似枚举的搜索尝试过程主要是在搜索尝试过程中寻找问题的解当发现已不满足求解条件时就“回溯”返回尝试别的路径。回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法 # 领域算法详解 A. 领域算法 梳理知识点在了解基础算法之后我们还要学习和了解在不同专业领域有哪些特有的算法。这里不一定要求复杂度而是要有知识面以及解决问题的思路。 一些领域算法 - Overview B. 领域算法之 安全算法主要包括摘要算法和加密算法两大类。 安全算法 - 摘要算法 消息摘要算法的主要特征是加密过程不需要密钥并且经过加密的数据无法被解密目前可以解密逆向的只有CRC32算法只有输入相同的明文数据经过相同的消息摘要算法才能得到相同的密文。消息摘要算法不存在密钥的管理与分发问题适合于分布式网络上使用。安全算法 - 加密算法 数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理使其成为不可读的一段代码为“密文”使其只能在输入相应的密钥之后才能显示出原容通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。 该过程的逆过程为解密即将该编码信息转化为其原来数据的过程安全算法 - 国密算法 国密即国家密码局认定的国产密码算法。主要有SM1SM2SM3SM4SM7, SM9。 C. 领域算法之 字符串匹配算法字符串匹配(String Matchiing)也称字符串搜索(String Searching)是字符串算法中重要的一种是指从一个大字符串或文本中找到模式串出现的位置。 朴素的字符串匹配算法Naive String Matching Algorithm) 朴素的字符串匹配算法又称为暴力匹配算法Brute Force Algorithm最为简单的字符串匹配算法Knuth-Morris-Pratt 字符串匹配算法即 KMP 算法 Knuth-Morris-Pratt算法简称KMP是最常用的字符串匹配算法之一Boyer-Moore 字符串匹配算法 各种文本编辑器的查找功能CtrlF大多采用Boyer-Moore算法效率非常高字符串匹配 - 文本预处理后缀树Suffix Tree 上述字符串匹配算法(朴素的字符串匹配算法, KMP 算法, Boyer-Moore算法)均是通过对模式Pattern字符串进行预处理的方式来加快搜索速度。对 Pattern 进行预处理的最优复杂度为 O(m)其中 m 为 Pattern 字符串的长度。那么有没有对文本Text进行预处理的算法呢本文即将介绍一种对 Text 进行预处理的字符串匹配算法后缀树Suffix Tree D. 领域算法之 大数据处理这里其实想让大家理解的是大数据处理的常用思路而不是算法本身。 大数据处理 - Overview 本文主要介绍大数据处理的一些思路大数据处理 - 分治/hash/排序 就是先映射而后统计最后排序:分而治之/hash映射: 针对数据太大内存受限只能是: 把大文件化成(取模映射)小文件即16字方针: 大而化小各个击破缩小规模逐个解决hash_map统计: 当大文件转化了小文件那么我们便可以采用常规的hash_map(ipvalue)来进行频率统计。堆/快速排序: 统计完了之后便进行排序(可采取堆排序)得到次数最多的IP。大数据处理 - Bitmap Bloom Filter 布隆过滤器有着广泛的应用对于大量数据的“存不存在”的问题在空间上有明显优势但是在判断存不存在是有一定的错误率(false positive)也就是说有可能把不属于这个集合的元素误认为属于这个集合(False Positive)但不会把属于这个集合的元素误认为不属于这个集合(False Negative)大数据处理 - 双层桶划分 其实本质上还是分而治之的思想重在“分”的技巧上适用范围: 第k大中位数不重复或重复的数字基本原理及要点: 因为元素范围很大不能利用直接寻址表所以通过多次划分逐步确定范围然后最后在一个可以接受的范围内进行。大数据处理 - Trie树/数据库/倒排索引 适用范围: 数据量大重复多但是数据种类小可以放入内存基本原理及要点: 实现方式节点孩子的表示方式扩展: 压缩实现大数据处理 - 外排序 适用范围: 大数据的排序去重基本原理及要点: 外排序的归并方法置换选择败者树原理最优归并树大数据处理 - Map Reduce MapReduce是一种计算模型简单的说就是将大批量的工作(数据)分解(MAP)执行然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后可以通过大量机器进行并行计算减少整个操作的时间。但如果你要我再通俗点介绍那么说白了Mapreduce的原理就是一个归并排序 E. 领域算法之 分布式算法接着向大家介绍分布式算法包括一致性Hash算法经典的Paxos算法Raft算法ZAB算法等顺便也介绍了经典用于全局ID生成的Snowflake算法。 分布式算法 - Overview 本文总结下常见的分布式算法分布式算法 - 一致性Hash算法 一致性Hash算法是个经典算法Hash环的引入是为解决单调性(Monotonicity)的问题虚拟节点的引入是为了解决平衡性(Balance)问题分布式算法 - Paxos算法 Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法使其获得2013年图灵奖。自Paxos问世以来就持续垄断了分布式一致性算法Paxos这个名词几乎等同于分布式一致性, 很多分布式一致性算法都由Paxos演变而来分布式算法 - Raft算法 Paxos是出了名的难懂而Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案分布式算法 - ZAB算法 ZAB 协议全称Zookeeper Atomic BroadcastZookeeper 原子广播协议, 它应该是所有一致性协议中生产环境中应用最多的了。为什么呢因为他是为 Zookeeper 设计的分布式一致性协议分布式算法 - Snowflake算法 Snowflake雪花算法是由Twitter开源的分布式ID生成算法以划分命名空间的方式将 64-bit位分割成多个部分每个部分代表不同的含义。这种就是将64位划分为不同的段每段代表不同的涵义基本就是时间戳、机器ID和序列数。为什么如此重要因为它提供了一种ID生成及生成的思路当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。 F. 领域算法之 其它算法汇总最后概要性的了解常见的其它算法负载均衡算法推荐算法数据挖掘或机器学习算法。因为有其专业性一般总体上了解就够了。 负载均衡算法 - 汇总 本文主要介绍常用的负载均衡算法和Nginx中支持的负载均衡算法轮询法(Round Robin)加权轮询法(Weight Round Robin)平滑加权轮询法(Smooth Weight Round Robin)随机法(Random)加权随机法(Weight Random)源地址哈希法(Hash)最小连接数法(Least Connections)数据挖掘 - 10大算法汇总 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART
