计算机程序 数据结构+算法 梳理汇总

2024-06-09 14:18

本文主要是介绍计算机程序 数据结构+算法 梳理汇总,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法(algorithm)简单来说就是定义良好的计算机过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。即算法就是一系列的计算步骤,用来将输入数据转换成输出数据。
书中有一句话非常好:
Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.
新手; 初学者; 初学修士(或修女); (修会等的) 初学生; 尚未赢过大赛的赛马;

是否具有扎实的算法知识和技术基础,是区分真正熟练的程序员与新手的一项重要特征。
以这句话激励自己要努力学习算法,夯实基础,成为真正熟练的程序员。

时间复杂度(cpu执行时长)、空间复杂度(运行时内存占用),最大复杂度、平均复杂度。

基础数据结构
1、线性表
列表/数组
链表(包含或不包含头节点,单向链表,单向循环链表,双向链表,双向循环链表,链表中查找、删除、插入节点、倒置)
跳跃表、并查集。
数组描述、链表描述。
2、栈
栈(数组/链表描述)
3、队列 FIFO
队列(链队列、循环队列)
4、优先级队列
元素出队的顺序由元素的优先级决定。不是元素进入队列的顺序。堆是实现优先级队列效率很高的数据结构。堆是一颗完全二叉树,用11.4.1节的数组表示最有效率。在链表结构中,在高度和重量上的左高树也适合于表示优先级队列。最小/最大优先级队列。

左高树

多级反馈队列
3、哈希表
碰撞解决方法:开放定址法、链地址法、再次哈希法、建立公共溢出区
布隆过滤器
动态哈希表
一致性哈希算法 chash库

4、树
,是n(n>=0)个节点的有限集合。在任意非空树中,(1)有且仅有一个特定的称为根(root)的节点;(2)当n>1时,其余节点可以分为m(m>0)个互不相交的有限集,每一个集合本身又是一棵树,称为根的子树。
二叉树,每个节点至多只有两棵子树。顺序存储、链式存储。先序、中序、后序遍历(先序遍历先访问根节点,之后访问左子树、右子树)。
满二叉树,深度为k,节点为2的k次方减1.
完全二叉树,节点编号与同深度的满二叉树一一对应。
哈夫曼树与编码
平衡二叉树,基于二分法的策略提高数据的查找速度的二叉树的数据结构;每一个非叶子节点,左子节点小于当前节点,右边子节点大于当前节点。
AVL树
B树(就是B-tree),B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),数据库索引技术里大量使用者B树和B+树的数据结构。
B+树,是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。
B+跟B树不同B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加;
B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样;
前缀树

平衡搜索树(AVL树/红黑树/分裂树/B树)
平衡树,最坏情况下的高度为O(logn)。
比较流行的一种平衡树是AVL树(AVL Tree),它是Adelson-Velskii和Landis在1962年提出的。

红黑树,一种自平衡二叉查找树,
线段树,线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。
子集树
排列树
竞赛树,也是完全二叉树,包含赢者树和输者树。基本操作是替换最大(或最小)元素。

内部排序,总数据量比较小,待排数据全在内存中。
外部排序,数据量比较大无法全部从磁盘加载到内存中,

插入排序:直接插入排序、折半插入排序(使用折半查找)、二路插入排序、希尔排序、表排序。
快速排序:是对起泡排序 Bubble Sort的一种改进,它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另外一部分的关键字小,则可分别对这两部分记录继续进行快速排序,以达到整个序列有序。
选择排序,简单选择排序,树形选择排序,堆排序
归并排序,将两个或两个以上的有序表组合成一个新的有序表。
基数排序,
桶排序,
计数排序,

归并排序采用了算法设计中的分治法,
分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题,递归的解决这些子问题,然后再去合并其结果,得到原问题的解。
分而治之方法与软件设计的模块化方法非常相似。
分治模式在每一层递归上有三个步骤:
分解(divide):将原问题分解成一系列子问题。
解决(conquer):递归地解答各子问题,若子问题足够小,则直接求解。
合并(combine):将子问题的结果合并成原问题的解。
归并排序(merge sort)算法按照分治模式,操作如下:
分解:将n个元素分解成各含n/2个元素的子序列
解决:用合并排序法对两个序列递归地排序
合并:合并两个已排序的子序列以得到排序结果

动态规划,每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

贪心算法 greedy method,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
在贪婪lan算法中,我们要逐步构造一个最优解。每一步,我们都在一定的标准下,做出一个最优决策。在每一步做出的决策,以后的步骤中都不可更改。做出决策所依据的标准称为贪婪准测(greedy criterion)。
线性规划
回溯su算法,实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。八皇后/四往后问题。
要求解一个问题,最可靠的一种方法是:列出所有候选解,然后逐个检查,在检查所有或部分候选解之后,便可以找到所需要的解。理论上,只要候选解的数量有限,而且在检查了所有或部分候选解之后可以缺点所需解,这种方法是可行的。不过在实际应用中,这种方法很少用,因为候选解的数量通常都非常大。
回溯法和分支定界法是堆候选解进行系统检查的两种方法。这两种方法使最坏情况下和一般情况下的求解时间大大减少。
1.定义解空间;2.组织解空间(使解空间便于搜索,典型的组织方法是图或树);
分支定界,和回溯法一样,分支定界法也经常把解空间组织成树结构,然后进行搜索。常用的树是子集树和排列树。与回溯法不同的是,回溯法使用深度优先搜索树,而分支定界法一般用广度优先或最小耗费方法来搜索树。
是另外一种系统地搜索解空间的方法。它与回溯法的主要区别在于E-节点的扩充方式。每个活动节点仅有一次变为E-节点。

这篇关于计算机程序 数据结构+算法 梳理汇总的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1045410

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举