数据结构与算法之美-学习笔记
接上篇⽂章，在我意识到数据结构与算法的重要性时，正好在⾥有⼈分享了极客时间的数据结构与算法之美的课程，从⼊门篇、基础篇、⾼级篇到实战篇，由浅⼊深的讲述常⽤的数据结构与算法，特别是在留⾔区作者的留⾔"迈不过去你我退钱"，我就喜欢这种有⾃信的⼈，当然不是完全指望他⼈帮⾃⼰把算法捡起来，
既然来了，就要全⾝⼼的投⼊，在此⽴个flag，通过这个阶段的学习，理解常⽤的算法与数据结构，掌握复杂度的分析，将提⾼代码执⾏效率思想融⼊⽇常开发中。
第1章 为什么要学习数据结构与算法
⽬的：我们学习数据结构与算法，并不是为了死记硬背⼏个知识点。我们的⽬的是建⽴时间复杂度、空间复杂度意识，写出⾼质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒⼈⽣经验，以此获得⼯作回报，实现个⼈价值。
第⼆章 如何抓住重点，系统⾼效的学习数据结构与算法
定义：从⼴义上讲，数据结构就是指⼀组数据的存储结构，算法就是操作数据的⼀组⽅法。
两者关系：数据结构与算法是相辅相成的，数据结构是为算法服务的，算法要作⽤在特定的数据结构之上。
数据结构是静态的，它只是组织数据的⼀种⽅式。如果不在它的基础上操作、构建算法，孤⽴存在的数据结构就是                      没⽤的。
学习重点：效率与资源消耗的度量衡-复杂度分析，10个数据结构：数组、链表、栈、队列、散列表、⼆叉树、堆、跳表、图、Trie树；10个算法：递归、排序、⼆份查、搜索、哈希算法、贪⼼算法、分治算法、回溯算法、动态规划、字符串匹配算法。
学习技巧:
1，边学边练，适度刷题。
2，多问、多思考、多互动。
3，打怪升级学习法，设⽴切实可⾏的⽬标。
4，知识需要沉淀，不要试图⼀下⼦掌握所有
第3章 复杂度分析（上）：如何分析、统计
复杂度分析的重要性：复杂度分析时整个算法学习的精髓，只要掌握了它，数据结构与算法的内容基本上就掌握了⼀半。
为何需要复杂度分析：
1，测试结果⾮常依赖测试环境。
2，测试结果受数据规模的影响很⼤。
⼤O表⽰法：T(n)=O(f(n))
T(n)表⽰代码执⾏时间，n表⽰数据规模的⼤⼩，f(n)代表每⾏代码执⾏的次数总和，O表⽰代码的执⾏时间T(n)与f(n)成正⽐。
整个意义：代表代码执⾏时间随数据规模增长的变化趋势。
复杂度分析法则：
1），单段代码看⾼频：⽐如循环
2），多段代码取最⼤：⽐如⼀段代码中有单循环与多重循环，那么取多重循环。
3），嵌套代码求乘积：⽐如递归、多重循环等。
4），多个规模求加法：⽐如⽅法有两个参数控制两个循环的次数，那么这时取⼆者复杂度相加。
常见的复杂度级别：
多项式阶：O(1)常数阶,O(logn)对数阶,O(n)线性阶,O(nlogn)线性对数阶,O(n^2)平⽅阶等
⾮多项式阶：随着数据规模的增长，算法的执⾏时间暴增，这类算法性能极差，包括指数阶，阶乘阶。
第5章 数组：为什么很多编程语⾔中数组都从0开始编号
本章开始的时候抛出了⼀个问题：为什么很多编程语⾔中数组都是从0开始编号？这个问题很有意思，虽然我经常⽤到数组，但是还真的没想到过为什么是从0开始的。
如何实现随机访问？
数组的定义：数组是⼀种线性表数据结构，它⽤⼀组连续的内存空间，来存储⼀组具有相同类型的数据。
第⼀是线性表。线性表就是数据排成像⼀条线⼀样的结构。每个线性表上的数据最多只有前和后两个⽅
向。除了数组，链表，队列，栈都是线性结构。
第⼆是连续的空间和相同的类型的数据。计算内存地址：a[i]_address = base_address + i * data_type_size（数组和链表的区别？）    数组删除(JVM标记清除垃圾回收算法)。插⼊删除的时间复杂度为O(n)
很多时候，我们并不是要记硬背某个数据结构的或者算法，⽽是要去学习它背后的思想和处理技巧，这些东西才是最有价值的。
如果使⽤1作为数组的开始：
a[k]_address = base_address + (k-1)*type_size，要多做⼀次减法运算。
第6章 链表(上)：如何实现LRU缓存淘汰算法？
链表结构：单链表、双向链表、循环链表。
单链表：头结点⽤来记录链表的基地址，尾节点指向空地址NULL 。
循环链表：尾节点指向头结点。著名的约瑟夫问题。
双向链表：具有后继指针next与前驱指针prev。linkhashpmap⽤到了双向列表。
对于执⾏较慢的程序，可以通过消耗更多的内存（空间换时间,⽐如缓存）来进⾏优化；
⽽消耗过多内存的程序，可以通过消耗更多的时间（时间换空间，⽐如⼿机单⽚机）来降低内存的消耗。
链表 & 数组
数组：插⼊删除O(n)，随机访问O(1). 缺点：⼤⼩固定，需要连续的内容空间。如果太⼩，如要扩容，则输⼊需要迁移。如果太⼤，则容易导致内存不⾜，使⽤效率不⾼。
链表：插⼊删除O(1)，随机访问O(n). 缺点：存储同样⼤⼩数据，需要更多空间，因为节点。链表的频繁插⼊删除容易导致内存碎⽚，造成GC .
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
ArrayList 详解
ArrayList是⼀个数组队列，相当于动态数组。ArrayList的操作不是线程安全的。
ArrayList包含了两个重要的对象：elementData 和 size。
(01) elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执⾏它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的⼤⼩会根据ArrayList容量的增长⽽动态的增长，具体的增长⽅式，请参考源码分析中的ensureCapacity()函数。
(02) size 则是动态数组的实际⼤⼩。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
数组和链表

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。