数据结构与算法
从广义上讲，数据结构就是一组数据的存储结构，算法就是操作数据的一组方法。
从狭义上讲，是指某些著名的数据结构和算法，比如队列、堆、栈、二分查找、动态规划等。
数据结构和算法本身解决的是快和省的问题，即让代码运行的更快，让代码更省存储空间。
所以，执行效率是算法一个非常重要的衡量指标。
时间和空间复杂度分析用来衡量算法的执行效率，可以粗略地估计算法的执行效率。
时间复杂度
时间复杂度的全称是渐进时间复杂度，表示算法执行时间与数据规模之间的增长关系。
- 只关注循环执行次数最多的一段代码，通常会忽略公式中的常量、低阶、系数，只需要记录一个最大阶的量级；
- 加法法则：总复杂度等于量级最大的那段代码的复杂度；
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
常见时间复杂度
常量阶O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
对数阶O(logn)
线性阶O(n)、O(m+n)、O(m*n)
线性对数阶O(nlogn)
平方阶O(n^2)、立方阶O(n^3)、k方阶O(n^k)
指数阶O(2^n)
阶乘阶O(n!)
越高阶复杂度的算法，执行效率越低。
从低到高有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)
空间复杂度
空间复杂度的全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
最好情况时间复杂度
最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
数组
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表：数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。链表、队列、栈也是线性表结构。
非线性表：比如二叉树、堆、图等，之所以叫非线性，是因为在非线性表中数据之间并不是简单的前后关系。
连续的内存空间和相同类型的数据：数组根据下标可以随机访问。
低效的插入和删除
插入：假设数组的长度为n，如果在中间第k个位置插入元素，那么k之后的元素都要往后移动一位，
如果在数组末尾插入元素，就不用移动数据了，最好时间复杂度为O(1)，
如果在数组的开头插入元素，那所有的数据都需要往后移动一位，最坏时间复杂度为O(n)。
优化方案：如果数组中存储的元素并没有任何规律，数组只是存储数据的集合，这种情况下，如果要在第k个位置插入一条数据，为了避免数据移动，
可以直接将第k个位置数据移动到数组元素的最后，然后把新的元素放入第k个位置，这种情况下在第k个位置插入元素的时间复杂度降为O(1)。删除
….
容器能否完全替代数组？
针对数组类型，很多语言提供了容器类，比如Java中的ArrayList、C++ STL中的vector。
容器类最大的优势是将很多数组操作的细节封装起来，比如对于插入和删除操作引起的数据移动不用开发人员自己实现，还有一个是支持动态扩容。
在创建ArrayList时，如果事先能够确定要存储数据的大小，最好在创建容器时指定大小，可以减少内存申请与数据移动。
适合使用数组的场景：
- Java ArrayList 无法存储基本数据类型，比如int、long 需要封装为Integer、Long类，而自动装箱和自动拆箱有一定的性能损耗。
如果特别关注性能，或者希望使用基本类型，就可以选择数组； - 如果数据大小事先已知，并且对数据操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组；
- 当表示多维数组时，用数组更加直观。
栈
栈是一种操作受限的数据结构，只支持入栈和出栈操作。先进后出是它最大的特点。
操作系统给每个线程分配了一块独立的内存空间，这块内存空间被组织成“栈”这种数据结构，用来存储函数调用时的临时变量。
每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
队列
先进先出
入队：放一个数据到队列的尾部。
出队：从队列头部取一个元素。
用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
循环队列
阻塞队列
并发队列
递归
三个条件：
- 一个问题的解可以分解为几个子问题的解；
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样；
- 存在递归终止条件。
如何编写递归代码
写出递推公式，找到终止条件，将递推公式转化成代码。
递归代码问题
- 堆栈溢出
- 重复计算
- 函数调用耗时多
- 空间复杂度高
排序算法
稳定性：待排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的顺序保持不变，则叫作稳定的排序算法，否则叫作不稳定的排序算法。
