什么是数据结构？什么是算法？
数据结构和算法是相辅相成的，数据结构是为了算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。
复杂度分析
常用的数据结构和算法
事半功倍的学习技巧
为什么需要复杂度分析？
通过实际的代码运行来统计运行效率的方法叫做是事后统计法，这种方法存在如下如下问题：
所以，我们需要一个不用具体的测试数据来测试，可以粗略地估计算法的执行效率的方法，这就是 时间、空间复杂度分析方法。
公式：T(n) = O(f(n))
这种复杂度表示方法只是表示一种变化趋势，当 n 很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以可以忽略。
示例代码 01
int cal(int n){
int sum = 0
int i = 1;
for(;i<=n;i++){
sum = sum + i;
}
}假设每行代码执行的时间都一样，为 unit_time，那么上述代码总的执行时间为：(2n+2)*unit_time，大 O 表示法为：T(n) = O(2n+2)，当 n 很大时，可记为 T(n) = O(n)
示例代码 02
int cal(int n){
int sum = 0;
int i = 1;
int j = 1;
for(;i<=n;++i){
j = 1;
for(;<=n;++j){
sum = sum + i*j
}
}
}假设每行代码执行的时间都一样，为 unit_time，那么上述代码总的执行时间为：(2n2+2n+3)*unit_time, 大 O 表示法为：T(n) = O(2n2+2n+3), 当 n 很大时，可记为 T(n) = O(n2)
渐进时间复杂度
对于上述罗列的复杂度量级，可以粗略地分为两类：多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无线增长。苏欧阳，非多项式时间复杂度的算法其实是效率非常低的算法。
渐进空间复杂度
表示算法的存储空间与数据规模之间的增长关系，常见的空间复杂度如下：
是一种线性表数据结构，用一组连续的内存空间来存储一组具有相同类型的数据。
使用建议：
为什么在大多数的编程语言中，数组要从 0 开发编号，而不是 1 ？
从数组存储的内存模型上来看，下标 最确切的定义应该是 偏移(offset)，这样就能确保正确计算出每次随机访问的元素对于的内存地址，这样就好理解了。
是一种线性数据结构，用一组非连续的内存空间来存储一组具有相同类型的数据。
数组 VS 链表 时间复杂度比较：
| 数组 | 链表 | |
|---|---|---|
| 插入、删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
常见的链表类型：
缓存策略常有如下三种方式：
如何基于链表实现 LRU 缓存淘汰算法？
思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问，当有一个新的数据被访问时，从链表头开始顺序遍历单链表。
如果此数据没有在缓存链表中，又可以分为两种情况：
时间复杂度为：O(n)
5 种常见的链表操作
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选 栈 这种数据结构
不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所有时间复杂度都是 O(1)。栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现，也可以通过链表实现。
内存中的堆栈和数据结构中的堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象出来的数据存储结构：
内存空间在逻辑上分为三部分：
先进者先出
不管是顺序队列还是链式队列，主要的两个操作是入队和出队，最大特点是先进先出。
几种高级的队列结构：
## 10 递归
递归需要满足的三个条件：
如何编写递归代码？
缺点：
常见排序算法：
| 排序算法 | 时间复杂度 | 是否基于比较 |
|---|---|---|
| 冒泡、插入、选择 | O(n2) | 是 |
| 快排、归并 | O(nlogn) | 是 |
| 桶、计数、基数 | O(n) | 否 |
如何分析一个 “排序算法”？
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一 个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
示例代码：
class Solution():
def bubbleSort(self, lis: list, n: int):
if n <= 1:
return
for i in range(len(lis)):
flag = False
for j in range(len(lis)-i-1):
if lis[j] > lis[j+1]:
lis[j], lis[j+1] = lis[j+1], lis[j]
flag = True
if not flag:
break
arr = [4, 5, 6, 3, 2, 1]
print(arr)
Solution().bubbleSort(arr, len(arr))
print(arr)插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
示例代码：
class Solution():
def insertionSort(self, lis: list, n: int):
if n <= 1:
return
for i in range(1, len(lis)):
val = lis[i]
j = i-1
while j >= 0:
if lis[j] > val:
lis[j+1] = lis[j]
j -= 1
lis[j+1] = val
attr = [4, 5, 6, 3, 2, 1]
print(attr)
Solution().insertionSort(attr, len(attr))
print(attr)选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末 尾。
示例代码：
class Solution():
def selectSort(self, lis: list, n: int):
if n <= 1:
return
for i in range(0, len(lis) - 1):
index = i
for j in range(i+1, len(lis)):
if lis[index] > lis[j]:
index = j
lis[i], lis[index] = lis[index], lis[i]
attr = [4, 5, 6, 3, 2, 1]
print(attr)
Solution().selectSort(attr, len(attr))
print(attr)| 是否原地排序 | 是否稳定 | 最好 | 最坏 | 平均 | |
|---|---|---|---|---|---|
| 冒泡 | 是 | 是 | O(n) | O(n2) | O(n2) |
| 插入 | 是 | 是 | O(n) | O(n2) | O(n2) |
| 选择 | 是 | 否 | O(n2) | O(n2) | O(n2) |
核心思想：利用分而治之的思想，递归解决问题。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一 起，这样整个数组就都有序了。
示例代码：
class Solution():
def mergeSort(self, arr):
print("Splitting ", arr)
if len(arr) > 1:
mid = len(arr)//2
lefthalf = arr[:mid]
righthalf = arr[mid:]
self.mergeSort(lefthalf)
self.mergeSort(righthalf)
i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
arr[k] = lefthalf[i]
i = i+1
else:
arr[k] = righthalf[j]
j = j+1
k = k+1
while i < len(lefthalf):
arr[k] = lefthalf[i]
i = i+1
k = k+1
while j < len(righthalf):
arr[k] = righthalf[j]
j = j+1
k = k+1
print("Merging ", arr)
arr = [4, 5, 6, 3, 2, 1]
print(arr)
Solution().mergeSort(arr)
print(arr)性能分析：
快排核心思想就是分治和分区。如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。 我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前 面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。
示例代码：
class Solution():
def quickSort(self, arr: list):
self.quickHelper(arr, 0, len(arr)-1)
def quickHelper(self, arr: list, first: int, last: int):
if first < last:
splitpoint = self.partition(arr, first, last)
self.quickHelper(arr, first, splitpoint-1)
self.quickHelper(arr, splitpoint+1, last)
def partition(self, arr: list, first: int, last: int):
pivot = arr[first]
left = first + 1
right = last
done = False
while not done:
while left <= right and arr[left] <= pivot:
left = left + 1
while arr[right] >= pivot and right >= left:
right = right - 1
if right < left:
done = True
else:
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
temp = arr[first]
arr[first] = arr[right]
arr[right] = temp
return right
arr = [4, 5, 6, 3, 2, 1]
print(arr)
Solution().quickSort(arr)
print(arr)性能分析：
但是，公式成立的前提是每次分区操作，我们选择的pivot都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的
核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之 后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶 内的数据值都是相同的，省掉了桶内排序的时间。
示例代码：
class Solution:
def countingSort(self, arr: list, n: int):
if n <= 1:
return
mv = arr[0]
for v in arr:
if mv < v:
mv = v
c = [0 for x in range(mv+1)]
for i in range(n):
c[arr[i]] += 1
for i in range(1, mv+1):
c[i] = c[i-1] + c[i]
r = [0 for x in range(n)]
i = n-1
while i >= 0:
index = c[arr[i]] - 1
r[index] = arr[i]
c[arr[i]] -= 1
i -= 1
for i in range(n):
arr[i] = r[i]
arr = [4, 5, 6, 3, 2, 1]
print(arr)
Solution().countingSort(arr, len(arr))
print(arr)计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低 位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。
| 时间复杂度 | 是否稳定排序 | 是否原地排序 | |
|---|---|---|---|
| 冒泡排序 | O(n2) | 是 | 是 |
| 插入排序 | O(n2) | 是 | 是 |
| 选择排序 | O(n2) | 否 | 是 |
| 快速排序 | O(nlog2) | 否 | 是 |
| 归并排序 | O(nlog2) | 是 | 否 |
| 计数排序 | O(n+k) k是数据范围 | 是 | 否 |
| 桶排序 | O(n) | 是 | 否 |
| 基数排序 | O(dn) d 是维度 | 是 | 否 |
如何优化快速排序？
二分查找（Binary Search）算法，也叫折半查找算法。时间复杂度为 O(longn)
示例代码：
class Solution:
def bsearch(self, arr: list, n: int, val: int):
return self.bsearchInternally(arr, 0, n-1, val)
def bsearchInternally(self, arr: list, low: int, high: int, val: int):
if low > high:
return -1
mid = low + ((high-low) >> 1)
if arr[mid] == val:
return mid
elif arr[mid] < val:
return self.bsearchInternally(arr, mid+1, high, val)
else:
return self.bsearchInternally(arr, low, mid-1, val)
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 4)
print(v)class Solution:
def bsearch(self, arr: list, n: int, val: int):
low = 0
high = n - 1
while low <= high:
mid = (low+high) // 2
if arr[mid] == val:
return mid
elif arr[mid] < val:
low = mid + 1
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 4)
print(v)应用场景的局限性：
二分查找的变形问题：
示例代码：
class Solution:
def bsearch(self, arr: list, n: int, val: int):
low = 0
high = n-1
while low <= high:
mid = low + ((high-low) >> 1)
if arr[mid] > val:
high = mid - 1
elif arr[mid] < val:
low = mid + 1
else:
if mid == 0 or arr[mid-1] != val:
return mid
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 4)
print(v)示例代码：
# 待修改
class Solution:
def bsearch(self, arr: list, n: int, val: int):
low, high = 0, n-1
while low <= high:
mid = low + ((high-low) >> 1)
if arr[mid] > val:
high = mid - 1
elif arr[mid] < val:
low = mid + 1
else:
if mid == n-1 or arr[mid+1] != val:
return mid
else:
low = mid + 1
return -1
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 3)
print(v)示例代码：
# 待修改
class Solution:
def bsearch(self, arr: list, n: int, val: int):
low, high = 0, n-1
while low <= high:
mid = low + ((high-low) >> 1)
if arr[mid] >= val:
if mid == 0 or arr[mid - 1] < val:
return mid
else:
high = mid-1
else:
low = mid + 1
return -1
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 3)
print(v)示例代码：
# 待修改
class Solution:
def bsearch(self, arr: list, n: int, val: int):
low, high = 0, n-1
while low <= high:
mid = low + ((high-low) >> 1)
if arr[mid] > val:
high = mid - 1
else:
if mid == n - 1 or arr[mid + 1] > val:
return mid
else:
low = mid + 1
return -1
arr = [1, 2, 3, 4, 2, 2, 3, 5]
v = Solution().bsearch(arr, len(arr), 3)
print(v)Redis 的有序集合就是使用跳表来实现的。
跳表使用空间换时间的设计思路，通过后见多级索引来提高查询订单效率，实现了基于链表的 “二分查找”。调表是一种动态结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(longn)
跳表的空间复杂度是 O(n)，不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现起来并不简单，但是作为一种动态结构，比起红黑树来说，实现要简单很多。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。
Word 文档中的单词拼写检查功能
散列表是由数组演化而来的，借助散列函数堆数组进行扩展，利用的是数组支持按照下标随机访问元素的特性。
散列冲突的解决方法：
散列表的查询效率不能笼统地说成是 O(1)，它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数涉及得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。
如何设计散列函数？
直接寻址法、平方取中法、折叠法、随机数法等
装载因子过大怎么办？
装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不要紧，对执行效率要求很高，可以降低负载因子的阀值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
如何避免低效地扩容？
通过均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，就避免了一次性扩容耗时过多的情况。这种实现方式，任何情况下，插入一个数据的时间 复杂度都是O(1)。
工业级散列表分析要素：
工业级散列表特征：
工业级散列表设计思路：
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而 通过原始数据映射之后得到的二进制值串就是哈希值。
满足如下几点要求：
应用场景：
想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。
二叉树的遍历：
实际上，二叉树的前、中、后序遍历就是一个递归的过程。
二叉查找树
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支 持快速插入、删除一个数据。
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大 于这个节点的值。
满足要求：
红黑树是一种平衡二叉查找树，它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的，红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来代替它。
堆的特点：
对于每个节点值都大于等于子树中每个节点值的堆，我们叫做 “大顶堆”；对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做 “小顶堆”。
为什么快速排序要比堆排序性能好？
堆的应用：
非线性数据结构
相关概念：
存储方法：
邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶 点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。
搜索方法：
广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，比起其他高级的搜索算法，比如A、IDA等，要简单粗暴，没有什么优化，所以，也被 叫作暴力搜索算法。所以，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。 广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终 止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是O(E)，空间复杂度是O(V)。
匹配算法
BF 算法
全称叫 Brute Force 算法，中文叫作暴力匹配算法，也叫朴素匹配算法。
RK 算法
全称叫 Rabin-Karp 算法，是 BF 算法的改进版。
BM 算法
全称叫 Boyer-Moore 算法。是一种非常搞笑的字符串匹配算法。
BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。
MKP 算法
KMP算法的核心思想是：我们假设主串是a，模式串是b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
BM算法有两个规则，坏字符和好后缀。KMP算法借鉴BM算法的思想，可以总结成好前缀规则。这里面最难懂的就是next数组的计算。如果用最笨的方法来计 算，确实不难，但是效率会比较低。所以，我讲了一种类似动态规划的方法，按照下标i从小到大，依次计算next[i]，并且next[i]的计算通过前面已经计算出来 的next[0]，next[1]，……，next[i-1]来推导。 KMP算法的时间复杂度是O(n+m)。
Trie树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
如果用来构建Trie树的这一组字符串中，前缀重复的情况不是很多，那Trie树这种数 据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。
尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在Trie树中做字符串匹配还是非常高效的，时间复杂度是O(k)，k表示要匹配的字符串的长度。 但是，Trie树的优势并不在于，用它来做动态集合数据的查找，因为，这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie树最有优势的是查找前缀匹配的字符 串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是Trie树比较经典的应用场景。
AC自动机是基于Trie树的一种改进算法，它跟Trie树的关系，就像单模式串中，KMP算法与BF算法的关系一样。KMP算法中有一个非常关键的next数组，类比 到AC自动机中就是失败指针。而且，AC自动机失败指针的构建过程，跟KMP算法中计算next数组极其相似。所以，要理解AC自动机，最好先掌握KMP算法，因为AC自动机其实就是KMP算法在多模式串上的改造。
整个AC自动机算法包含两个部分，第一部分是将多个模式串构建成AC自动机，第二部分是在AC自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模 式串构建成Trie树，另一个是在Trie树上构建失败指针。
贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim和Kruskal最小生成树算法、还 有Dijkstra单源最短路径算法。
实际上，贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些 子问题，然后再合并其结果，就得到原问题的解。
分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：
分治算法能解决的问题，一般需要满足下面这几个条件：
回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来 实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
原文：https://www.cnblogs.com/hippieZhou/p/10970145.html