《算法与数据结构 精要笔记》 （一）基础概念
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法与数据结构 精要笔记》 （一）基础概念，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2509字，纯文字阅读大概需要4分钟。
内容图文
题记：题主工作三年，前段时间面试bat被面试官算法“血虐”，差点心灰意冷，怀疑人生，但是幸好意志坚强，遂，决定发愤图强，学好算法。每天坚持学一些，每周坚持有深度学习四小时。先慢慢来，学好基本的概念，常用的数据结构和算法，但是图的话，就不涉猎了，因为真的比较难，学习成本太高，讲究性价比嘛。
之后主要是记录学习常用数据结构和算法。像栈，队列，树精要笔记。内容也不会过于基础，特别基础的会一带而过，主要是记录的是常用，重点。
Go...
一.算法
衡量算法的优劣
I.时间复杂度
O(1),O(n),O(n*LOG(n),n*n)
II.空间复杂度
常量空间O(1)，线性空间O(n)，二维空间O(n*n)，递归空间（与递归深度成正比）。
一般情况下，时间复杂度重要一些，宁愿少分配一些内存空间，也要程序执行速度。
二.数据结构
数据结构是算法的基石。如果把算法比喻成美丽的跳舞者，那么数据结构就是舞台。
I.线性结构 (一对一)
数组
链表
栈
先进后出，插入删除的操作时间复杂度都是O(1)
队列
先进先出，插入删除的操作时间复杂度都是O(1)
II.非线性结构(一对多）
二叉树，二叉堆等
III.非线性结构(多对多，图太复杂，忽略，之后也不会讲任何图的知识)
图
三.逻辑结构和物理结构
逻辑结构是抽象的概念，依赖于物理结构，所有的逻辑结构都是由物理结构扩展衍变而来。
物理结构
I.数组（顺序存储）
II.链表（链式存储）
由上图看时间复杂度，可得出，数组适用于读取（查）较多的需求，链表适用于修改（增，删）较多的需求。
逻辑结构
栈，队列，树等。所有的逻辑结构都是由两种基本的物理结构构成。比如，树，可以由链表表示，也可以由数组表示。
四.哈希表
哈希表也叫“散列表”。这种数据机构提供了健值得映射关系。只要给出一个key，就能高效的查找出它所匹配的value，时间复杂度接近于O(1)。对于时间复杂度转为空间复杂度的时候起到很重要的作用。因此用途非常广泛。物理结构--数组是下标int和值，通过此概念，将key转为下标，称之为哈希函数。而数组是有限的，因此，哈希表的长度也是有限的，哈希表的key转为下标也是有限的。因为多个key可能转为同一个下标，则造成冲突，称为“哈希冲突”。
常用解决哈希冲突方案：
I.开放寻址法
当一个key通过哈希函数找到对应的数组下标已经被占用时，我们用下一个没有被占用的坑位。
II.链表法
哈希数组中存储的对象是链表的形式，这样每一个对象可以存储多个值，当多个key转为同一个下标时，都存储在该链表节点中。
哈希表的读取操作：
I.通过哈希函数，将key转为对应的int下标。
II.找到数组下标对应的元素，如果这个元素的key不是我们想要找的“key”，则根据哈希冲突的方案，顺着找下一个。（链表法则在该链表结点找下一个对应的值）
哈希表的扩容：
I.扩容，首先创建一个新的空数组，是原来的两倍。
II.重新Hash，因为长度扩大后，hash的规则改变。
五.总结
以上，数据结构的基本概念全部讲完，自我感觉数据结构最基本的本质是数组和链表，而算法就是将这基本的数组和链表如何拓展衍变为栈，队列，树等复杂的数据机构，衍变过程中的时间复杂度和空间复杂度就代表了该算法的好坏。
内容总结
以上是互联网集市为您收集整理的《算法与数据结构 精要笔记》 （一）基础概念全部内容，希望文章能够帮你解决《算法与数据结构 精要笔记》 （一）基础概念所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。