- 时间复杂度与代码的结构设计高度相关；空间复杂度与代码中数据结构的选择高度相关。
- 一个顺序结构的代码，复杂度是O(1)。
- 二分查找，或者更通用地说是采用分而治之的二分策略，复杂度都是O(logn)。
- 一个简单的for循环，复杂度是O(n)。
- 两个顺序执行的for循环，复杂度是O(n)+O(n)=O(2n)，其实也是O(n)。
- 两个嵌套的for循环，复杂度是O(n²)。
- 在程序开发中，连接时间和空间的桥梁就是数据结构。对于一个开发任务，如果能找到一种高效的数据组织方式，采用合理的数据结构的话，那就可以实现时间复杂度的再次降低。同样的，这通常会增加数据的存储量，也就是增加了空间复杂度。
- 数据处理的基本操作只有3个，分别是增、删、查。其中，增和删又可以细分为在数据结构中间的增和删，以及在数据结构最后的增和删。区别就在于原数据的位置是否发生改变。查找又可以细分为按照位置条件的查找和按照数据数值特征的查找。几乎所有的数据处理，都是这些基本操作的组合和叠加。
- 优化方法论：
- 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
- 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
- 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。
数组是一种容器，可以用来存放若干个相同类型的数据元素。- 数组在内存中是
连续存放的，数组内的数据，可以通过索引值直接取出得到。 - 数组在存储数据时是按顺序存储的，并且存储数据的内存也是连续的，这就造成了它具有
增删困难、查找容易的特点。 - 在最后若插入数据，则时间复杂度为
O(1)；如果中间某处插入数据，则时间复杂度为O(n)。 - 删除对应位置，扫描全数组，时间复杂度为
O(n)。 - 如果只需根据索引值进行一次查找，时间复杂度是
O(1)。但是要在数组中查找一个数值满足指定条件的数据，则时间复杂度是O(n)。
KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。前缀表记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
- 线性表是n个数据元素的有限序列，最常用的是链式表达，通常也叫作线性链表或者
链表。 - 在单链表中存储的数据元素也叫作结点，一个结点存储的就是一条数据记录。每个结点的结构包括两个部分：
- 第一是具体的数据值；
- 第二是指向下一个结点的指针。
- 在链表的最前面，通常会有个
头指针用来指向第一个结点。对于链表的最后一个结点，由于在它之后没有下一个结点，因此它的指针是个空指针。 - 对于一个单向链表，让最后一个元素的指针指向第一个元素，就得到了
循环链表。 - 把结点的结构进行改造，除了有指向下一个结点的指针以外，再增加一个指向上一个结点的指针。这样就得到了
双向链表。 - 可以对双向链表和循环链表进行融合，就得到了
双向循环链表。 - 链表在
新增、删除数据都比较容易，可以在O(1)的时间复杂度内完成。但对于查找，不管是按照位置的查找还是按照数值条件的查找，都需要对全部数据进行遍历。这显然就是O(n)的时间复杂度。 虽然链表在新增和删除数据上有优势，但仔细思考就会发现，这个优势并不实用。这主要是因为，在新增数据时，通常会伴随一个查找的动作。- 如果数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适。如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合些。
- 栈是一种特殊的
线性表。栈与线性表的不同，体现在增和删的操作。 - 栈的数据结点必须
后进先出。 - 栈的数据新增和删除操作只能在这个线性表的表尾进行，即在线性表的基础上加了限制。
- 栈既然是线性表，那么它也包含了表头和表尾。不过在栈结构中，由于其操作的特殊性，会对表头和表尾的名字进行改造。表尾用来输入数据，通常也叫作栈顶（top）；相应地，表头就是栈底（bottom）。栈顶和栈底是用来表示这个栈的两个指针。跟线性表一样，栈也有顺序表示和链式表示，分别称作顺序栈和链栈。
- 对于链式栈来说，新增删除数据元素没有任何循环操作，其时间复杂度均为O(1)。对于查找操作，相对链表而言，链栈没有额外的改变，它也需要遍历整个栈来完成基于某些条件的数值查找。
- 不管是顺序栈还是链栈，数据的新增、删除、查找与线性表的操作原理极为相似，时间复杂度完全一样，都依赖当前位置的指针来进行数据对象的操作。区别仅仅在于新增和删除的对象，只能是栈顶的数据结点。
单调栈的定义：单调栈就是指栈中的元素必须是按照升序排列的栈，或者是降序排列的栈。
- 队列是一种特殊的线性表，与线性表的不同之处也是体现在对数据的增和删的操作上。
- 队列的特点是
先进先出，队列的数据新增操作只能在末端进行，不允许在队列的中间某个结点后新增数据。 - 与线性表、栈一样，队列也存在这两种存储方式，即顺序队列和链式队列。
- 顺序队列，依赖数组来实现，其中的数据在内存中也是顺序存储。而链式队列，则依赖链表来实现，其中的数据依赖每个结点的指针互联，在内存中并不是顺序存储。链式队列，实际上就是只能尾进头出的线性表的单链表。
- 队列从队头（
front）删除元素，从队尾（rear）插入元素。 - 对于一个顺序队列的数组来说，会设置一个front指针来指向队头，并设置另一个rear指针指向队尾。不断进行插入删除操作时，头尾两个指针都会不断向后移动。
循环队列进行新增数据元素操作时，首先判断队列是否为满。如果不满，则可以将新元素赋值给队尾，然后让rear指针向后移动一个位置。如果已经排到队列最后的位置，则rear指针重新指向头部。- 循环队列进行删除操作时，即出队列操作，需要判断队列是否为空，然后将队头元素赋值给返回值，front指针向后移一个位置。如果已经排到队列最后的位置，就把front指针重新指向到头部。
- 当循环队列为空时，有front指针和rear指针相等。而队列满时，同样有front指针和rear指针相等。常用的方法是，设置一个标志变量flag来区别队列是空还是满。
- 链式队列就是一个单链表，同时增加了front指针和rear指针。链式队列和单链表一样，通常会增加一个头结点，并令front指针指向头结点。头结点不存储数据，只是用来辅助标识。
- 链式队列进行新增数据操作时，将新结点赋值给原队尾结点的后继。然后把新结点设置为队尾结点。
- 当链式队列进行删除数据操作时，实际删除的是头结点的后继结点。这是因为头结点仅仅用来标识队列，并不存储数据。因此，出队列的操作，就需要找到头结点的后继，这就是要删除的结点。接着，让头结点指向要删除结点的后继。
- 如果链式队列除去头结点外只剩一个元素，那么删除仅剩的一个元素后，rear指针就变成野指针了。这时候，需要让rear指针指向头结点。
单调队列要求队列中的元素必须满足单调性，比如单调递增，或者单调整递减。- 对于队列的查找操作，不管是顺序还是链式，队列都没有额外的改变。跟线性表一样，它也需要遍历整个队列来完成基于某些条件的数值查找。因此时间复杂度也是O(n)。
- 在时间复杂度上，循环队列和链式队列的新增、删除操作都为O(1)。而在查找操作中，队列和线性表一样只能通过全局遍历的方式进行，也就是需要O(n)的时间复杂度。在空间性能方面，循环队列必须有一个固定的长度，因此存在存储元素数量和空间的浪费问题，而链式队列不存在这种问题，所以在空间上，链式队列更为灵活一些。
- 通常情况下，在可以确定队列长度最大值时，建议使用循环队列。无法确定队列长度时，应考虑使用链式队列。
树是由结点和边组成的，不存在环的一种数据结构。树满足递归定义的特性。- 在
二叉树中，每个结点最多有两个分支，即每个结点最多有两个子结点，分别称作左子结点和右子结点。 满二叉树，定义为只有最后一层无任何子结点，其他所有层上的所有结点都有两个子结点的二叉树。完全二叉树，定义为除了最后一层以外，其他层的结点个数都达到最大，并且最后一层的叶子结点都靠左排列。- 树的遍历的时间复杂度是
O(n)。在指定位置的数据增删操作时间复杂度都是O(1)。 对于查找操作，如果是普通二叉树，则查找的时间复杂度和遍历一样，都是O(n)。如果是二叉查找树，则可以在O(logn)的时间复杂度内完成查找动作。
- 优先级队列都是基于堆（
Heap）这种数据结构来实现的。 - 堆的分类：大堆与小堆。
- 通常堆的结构都是表现为一棵树，如果根比左右子结点都大，那么称为
大堆。如果根比左右子结点都要小，那么称为小堆。 - 每次有元素
push或者pop的时候，调整堆的时间复杂度为O(lgn)，速度也非常快。因此，堆经常被用于优先级队列。 - 大部分时候都是使用数组表示一个堆，而不是使用二叉树。这是因为数组的内存具有连续性，访问速度更快；堆结构是一棵
完全二叉树。
哈希表的设计采用了函数映射的思想，将记录的存储位置与记录的关键字关联起来。这样的设计方式，能够快速定位到想要查找的记录，而且不需要与表中存在的记录的关键字比较后再来进行查找。- 哈希表提供非常快速的插入-删除-查找操作，无论多少数据，插入和删除值需要接近
常量的时间。在查找方面，哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。 - 哈希表中的数据是没有顺序概念的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。哈希表中的key是不允许重复的。
- 递归的核心思想是把规模大的问题转化为规模小的相似的子问题来解决。
- 在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。
- 分治法的核心思想就是分而治之。将一个难以直接解决的大问题，分割成一些可以直接解决的小问题。如果分割后的问题仍然无法直接解决，那么就继续递归地分割，直到每个小问题都可解。
- 采用分治法时，一般原问题都需要具备以下几个特征：
- 难度在降低，即原问题的解决难度，随着数据的规模的缩小而降低。这个特征绝大多数问题都是满足的。
- 问题可分，原问题可以分解为若干个规模较小的同类型问题。这是应用分治法的前提。
- 解可合并，利用所有子问题的解，可合并出原问题的解。这个特征很关键，能否利用分治法完全取决于这个特征。
- 相互独立，各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题。如果子问题之间不独立，则分治法需要重复地解决公共的子问题，造成效率低下的结果。
- 原问题的数据是否有序，预期的时间复杂度是否带有logn项，是否可以通过小问题的答案合并出原问题的答案。如果这些先决条件都满足，应该第一时间想到分治法。
- 衡量一个排序算法的优劣，主要会从以下3个角度进行分析：
- 1．时间复杂度，具体包括，最好时间复杂度、最坏时间复杂度以及平均时间复杂度。
- 2．空间复杂度，如果空间复杂度为1，也叫作原地排序。
- 3．稳定性，排序的稳定性是指相等的数据对象，在排序之后，顺序是否能保证不变。
- 从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。
- 冒泡排序就像是在一个水池中处理数据一样，每次会把最大的那个数据传递到最后。
- 冒泡排序最好时间复杂度是O(n)，也就是当输入数组刚好是顺序的时候，只需要挨个比较一遍就行了，不需要做交换操作，所以时间复杂度为O(n)。
- 冒泡排序最坏时间复杂度是O(n²)。也就是说当数组刚好是完全逆序的时候，每轮排序都需要挨个比较n次，并且重复n次，所以时间复杂度为O(n²)。
- 当输入数组杂乱无章时，冒泡排序的平均时间复杂度也是O(n²)。
- 冒泡排序不需要额外的空间，所以空间复杂度是O(1)。冒泡排序过程中，当元素相同时不做交换，所以冒泡排序是稳定的排序算法。
- 选取未排序的元素，插入到已排序区间的合适位置，直到未排序区间为空。
- 插入排序就是从左到右维护一个已经排好序的序列。直到所有的待排数据全都完成插入的动作。
- 插入排序最好时间复杂度是O(n)，即当数组刚好是完全顺序时，每次只用比较一次就能找到正确的位置。这个过程重复n次，就可以清空未排序区间。
- 插入排序最坏时间复杂度则需要O(n²)。即当数组刚好是完全逆序时，每次都要比较n次才能找到正确位置。这个过程重复n次，就可以清空未排序区间，所以最坏时间复杂度为O(n²)。
- 插入排序的平均时间复杂度是O(n²)。这是因为往数组中插入一个元素的平均时间复杂度为O(n)，而插入排序可以理解为重复n次的数组插入操作，所以平均时间复杂度为O(n²)。
- 插入排序不需要开辟额外的空间，所以空间复杂度是O(1)。
- 插入排序是稳定的排序算法。
- 首先将数组不断地二分，直到最后每个部分只包含1个数据。然后再对每个部分分别进行排序，最后将排序好的相邻的两部分合并在一起，这样整个数组就有序了。
- 对于归并排序，采用了二分的迭代方式，复杂度是
O(logn)。 - 每次的迭代，需要对两个有序数组进行合并，这样的动作在
O(n)的时间复杂度下就可以完成。因此，归并排序的复杂度就是二者的乘积O(nlogn)。执行频次与输入序列无关，因此，归并排序最好、最坏、平均时间复杂度都是O(nlogn)。 - 由于每次合并的操作都需要开辟基于数组的临时内存空间，所以空间复杂度为
O(n)。归并排序合并的时候，相同元素的前后顺序不变，所以归并是稳定的排序算法。 - 把有序性也当成信息，那么合并排序本质上就是一个
后序遍历。
- 快速排序法的原理也是分治法。它的每轮迭代，会选取数组中任意一个数据作为分区点，将小于它的元素放在它的左侧，大于它的放在它的右侧。再利用分治思想，继续分别对左右两侧进行同样的操作，直至每个区间缩小为1，则完成排序。
- 在快排的最好时间的复杂度下，如果每次选取分区点时，都能选中中位数，把数组等分成两个，那么此时的时间复杂度和归并一样，都是O(nlogn)。
- 在最坏的时间复杂度下，也就是如果每次分区都选中了最小值或最大值，得到不均等的两组。那么就需要n次的分区操作，每次分区平均扫描n/2个元素，此时时间复杂度就退化为**O(n²)**了。
- 快速排序法在大部分情况下，统计上是很难选到极端情况的。因此它平均的时间复杂度是O(nlogn)。
- 快速排序法的空间方面，使用了交换法，因此空间复杂度为O(1)。
- 快速排序的分区过程涉及交换操作，所以快排是不稳定的排序算法。
- 如果对数据规模比较小的数据进行排序，可以选择时间复杂度为O(n²)的排序算法。因为当数据规模小的时候，时间复杂度O(nlogn)和O(n²) 的区别很小，对实际的性能影响并不大。
- 对数据规模比较大的数据进行排序，就需要选择时间复杂度为O(nlogn)的排序算法了。
- 归并排序的空间复杂度为O(n)，也就意味着当排序100M的数据，就需要200M的空间，所以对空间资源消耗会很多。
- 快速排序在平均时间复杂度为O(nlogn)，但是如果分区点选择不好的话，最坏的时间复杂度也有可能逼近O(n²)。而且快速排序不具备稳定性，这也需要看所面对的问题是否有稳定性的需求。