01.为什么学习数据结构和算法？

为了突破编程的瓶颈，不再只写功能性代码
为了体验编程的魅力，打开新世界的大门
为了不被淘汰，掌握别人认为难以学会的，才更有价值

02.如何抓住重点，系统高效的学习数据结构和算法？

1）理解概念

什么是数据结构？
广义上指一组数据的存储结构
狭义上是指队列，堆栈等
什么是算法？
广义上是一组操作数据的方法
狭义上是指二分查找，排序等

2）数据结构和算法的关系

相辅相成
数据结构是为算法服务的，算法作用在特定的数据结构之上
例如，常用的二分查找要用数组来存储数据才能正常工作

3）学习的重点是什么？

复杂度分析的方法

是精髓，半壁江山，心法，考量效率和资源消耗的方法	

20个常用的数据结构和算法

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”

不要为了记忆知识而学习，训练思维逻辑，要多辩证思考，多问为什么

4）事半功倍的学习技巧

边学边练，适度刷题
多问，多思考，多互动
打怪升级学习法：精彩留言，学习笔记
知识需要沉淀，不要试图一下子掌握所有

03.复杂度分析（上）：如何分析，统计算法的执行效率和资源消耗？

数据结构和算法是解决更快和更省的问题，即让代码运行的更快，让代码更省空间

1）为什么需要复杂度分析法？

不用具体的测试数据，粗略的估算算法执行效率的方法

2）大O复杂度表示法

所有代码的执行总时间T(n)与每行代码的执行次数n成正比

T(n)=O(f(n))
T(n)代表代码执行的总时间
n表示数据的规模大小
f(n)表达式表示每行代码执行的次数总和
O表示T(n)和f(n)成正比

时间复杂度并不是表示代码真正执行的时间，而是表示代码执行时间随数据规模增长的变化趋势

3）时间复杂度分析

时间复杂度表示算法执行时间和数据规模的之间的增长关系

只关注循环执行次数最多的一段代码

时间复杂度是表示一个算法执行效率和数据规模增长的的变化趋势，忽略常量，系数，低阶只记录最大阶的量级

加法法则：总复杂度等于量级最大的那段代码的复杂度

如果T1(n)=O(f(n)),T2(n)=O(f(n));
那么T(n)=T1(n)+T2(n)=max(O(f(n),g(n)))=O(max(f(n),g(n))).

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

如果T1(n)=O(f(n)),T2(n)=O(f(n));
那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

4)几种常见的时间复杂度实例分析

常见的复杂度量级，按量级递增

多项式量级

常量阶O(1),对数阶O(logn),线性阶O(n),线性对数阶O(nlongn),平方阶O(n2),立方阶O(n3),K次方阶O(n*k)

非多项式量级

指数阶O(2*n),阶乘阶O(n!)

常见的多项式时间复杂度

O(1)
代码的执行时间不随n的增大而增长
一般代码中不存在循环语句，递归语句即使成千上万行代码，
其时间复杂度也是O(1)
O(logn),O(nlogn)
该时间复杂度的常见算法：归并排序，快速排序
O(m+n),O(m*n)
代码复杂度由m，n两个数据规模来决定

5）空间复杂度分析

空间复杂度表示算法的存储空间与数据规模之间的增长关系
常见的空间复杂度就是 O(1)、O(n)、O(n2)
像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到

04.复杂度分析啊（下）：浅析最好、最坏、平均、均摊时间复杂度

来历：同一段代码，在不同输入情况下，复杂度量级有可能不一样。

最好、最快情况时间复杂度

最好情况时间复杂度就是，在最理想的情况下，执行代码的时间复杂度
比如数组中查找一个元素，正好在第一个位置最好情况时间复杂度就是，在最糟糕的情况下，执行代码的时间复杂度
比如数组中查找一个元素，数组中不存在这个元素

平均情况时间复杂度

每种情况需要加权计算，全称加权平均时间复杂度
只有同一块代码在不同的情况下有量级的差别，我们才会使用最好，最坏，平均三种						复杂度表示法来区分。大多数情况我们使用一个复杂度就能满足需求。

均摊时间复杂度

使用摊还分析法对一个数据结构进行一组操作，大部分情况时间复杂度很低，个别情况时间复杂度比较高，而且这些操作存在前后连贯的时序关系，看是否能够将复杂度高的耗时，均摊到那些复杂度低的操作上。一般情况，均摊时间复杂度等于最好情况时间复杂度均摊时间复杂度就是一种特殊的平均时间复杂度

使用什么情况的时间复杂度不重要，初衷还是要更好的体现这个算法或者代码的性能

05.为什么很多编程语言中数组都是从0开始编号？

来历：

1）如何实现随机访问？

数组概念：是一种线性表数据结构，它用一组连续的内存空间，来存储一组相同的数据。

计算机给每个内存单元分配一个内存地址，通过内存地址来访问内存中的数据，当计算机需要随机访问数据中的某个元素时，就会通过下面的寻址公式计算出该元素的内存地址

a[i]_address=base_address + i * data_type_size
base_address:内存块的首地址
data_type_size:存储数据类型的占用的内存大小

2)低效的“插入”和“删除”

数组为了保持内存数据的连续性，在插入或者删除元素后，会造成后面数据的搬移，导致低效。

插入，删除元素操作
最好情况时间复杂度：O(1)
最坏情况时间复杂度：O(n)
平均时间复杂度：O(n)

JVM标记垃圾清除算法：每次删除操作并不真正搬移数据，只是记录数据，等到空间不足，才真正执行一次删除操作，这样就大大减少删除操作导致的数据搬移。

不要死记硬背数据结构和算法，学习其背后的思想和处理技巧，
这些东西才是最有价值的

3）警惕数据访问的越界问题

	访问数据的本质就是访问一段内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就不会报任何错误。C中数组越界检查由程序员做java本身会做越界检查

4）解答开篇

	数组的下标为什么从0，而不是从1开始？效率优化角度：使用0，寻址操作会减少一次减法操作学习成本的角度：其他语言效仿C语言从0开始计数数组下标，减少学习成本，沿用了从0计数的习惯