《数据结构与算法之美》学习笔记
02 如何抓住重点，系统⾼效地学习数据结构与算法
什么是数据结构？什么是算法？
从⼴义上讲，数据结构就是指⼀组数据的存储结构算法就是操作数据的⼀组⽅法；
从侠义上讲，是指某些著名的数据结构和算法，⽐如队列、栈、堆、⼆分查、动态规划等；
数据结构和算法是相辅相成的，数据结构是为了算法服务的，算法要作⽤在特定的数据结构之上。因此，我们⽆法孤⽴数据结构来讲算法，也⽆法孤⽴算法来讲数据结构。
复杂度分析
⽤于考量⼀效率和资源消耗的⽅法；
常⽤的数据结构和算法
数组、链表、栈、队列、散列表、⼆叉树、堆、调表、图、Trie 树；
递归、排序、⼆分查、搜索、哈希算法、贪⼼算法、分治算法、回溯算法、动态规划、字符串匹配算法；
事半功倍的学习技巧
边学边练。适度刷题；
多问、多思考、多互动；
⼤概升级学习法
知识需要沉淀，不要试图⼀下⼦掌握所有；
03 & 04 复杂度分析
如何分析、统计算法的执⾏效率和资源消耗？
为什么需要复杂度分析？
通过实际的代码运⾏来统计运⾏效率的⽅法叫做是事后统计法，这种⽅法存在如下如下问题：
测试结构⾮常依赖测试环境；
测试结构受数据规模的影响很⼤；
所以，我们需要⼀个不⽤具体的测试数据来测试，可以粗略地估计算法的执⾏效率的⽅法，这就是时间、空间复杂度分析⽅法。
⼤ O 复杂度表⽰法
公式：T(n) = O(f(n))
n：表⽰数据规模的⼤⼩；
T(n)：表⽰代码执⾏的时间；
f(n)：表⽰每⾏代码执⾏的次数总和；
O：表⽰代码的执⾏时间 T(n) 与 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)
时间复杂度分析
渐进时间复杂度
数组和链表只关注循环执⾏次数最多的⼀段代码；
加法法则：总复杂度等于量级最⼤的那段代码的复杂度；（如果 T1(n) = O(f(n)),T2(n) = O(g(n)); 那么 T(n) = T1(n) + T2(n) = max(O(f(n)),O(g(n))) = O(max(f (n),g(n)))）
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；（如果 T1(n) = O(f(n)),T2(n) =O(g(n))；那么 T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))）
⼏种常见时间复杂度实例分析
复杂度量级（按数量级递增）
常量阶 O(1)
指数阶 O(2n)
对数阶 O(log n)
阶乘阶 O(n!)
线性阶 O(n)
线性对数阶 O(nlog n)
平⽅阶 O(n2)
⽴⽅阶 O(n3)
k次⽅阶 O(n k)
......
对于上述罗列的复杂度量级，可以粗略地分为两类：多项式量级和⾮多项式量级。其中，⾮多项式量级只有两个：O(2n) 和 O(n!)。当数据规模 n 越来越⼤时，⾮多项式量级算法的执⾏时间会急剧增加，求解问题的执⾏时间会⽆线增长。苏欧阳，⾮多项式时间复杂度的算法其实是效率⾮常低的算法。
空间复杂度分析
渐进空间复杂度
表⽰算法的存储空间与数据规模之间的增长关系，常见的空间复杂度如下：
O(1)
O(n)
O(n2)
浅析最好、最坏、平均、均摊时间复杂度
最坏、最好情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
05 数组
是⼀种线性表数据结构，⽤⼀组连续的内存空间来存储⼀组具有相同类型的数据。
⽀持随机访问；
低效的插⼊和删除，平均复杂度为 O(n)；
警惕数组的访问越界问题；
使⽤建议：
如果特别关注性能，或者希望使⽤基本类型，可以选⽤数组；
如果数据⼤⼩事先已知，并且对数据的操作⾮常简单，可以直接使⽤数组；
当要表⽰多维数组时，⽤数组往往会更加直观；
对于业务开发，直接使⽤集合类型就⾜够了，省时省⼒；如果时作⼀些⾮常底层的开发，这个时候数组就会优于集合；
为什么在⼤多数的编程语⾔中，数组要从 0 开发编号，⽽不是 1 ？
从数组存储的内存模型上来看，下标最确切的定义应该是偏移(offset)，这样就能确保正确计算出每次随机访问的元素对于的内存地址，这样就好理解了。06 & 07 链表
是⼀种线性数据结构，⽤⼀组⾮连续的内存空间来存储⼀组具有相同类型的数据。
不存储越界问题；
相⽐数组，插⼊和删除较为⾼效；
数组 VS 链表时间复杂度⽐较：
数组链表
插⼊、删除O(n)O(1)
随机访问O(1)O(n)
常见的链表类型：
单链表
循环链表
双向链表
双向循环链表（以空间换时间）
缓存问题
缓存策略常有如下三种⽅式：
先进先出策略 FIFO（First In,First Out）
最少使⽤策略 LFU（Least Frequently Used）
最近最少使⽤策略 LRU（Least Recently Used）
如何基于链表实现 LRU 缓存淘汰算法？
思路：维护⼀个有序单链表，越靠近链表尾部的结点是越早之前访问，当有⼀个新的数据被访问时，从链表头开始顺序遍历单链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插⼊到链表的头部。
如果此数据没有在缓存链表中，⼜可以分为两种情况：
如果此时缓存未满，则将此结点直接擦汗如到链表的头部；
如果此时缓存已满，则链表尾结点删除，将⼼的数据结点插⼊到链表头部。
时间复杂度为：O(n)
如何轻松写出正确的链表代码？
理解指针或引⽤的含义
警惕指针丢失和内存泄漏
利⽤哨兵简化实现难度
重点留意边界条件处理
举例画图，辅助思考
多写多练，没有捷径
5 种常见的链表操作
单链表反转
链表中环的检测
两个有序链表合并
删除链表倒数第 n 个结点
求链表的中间结点
08 栈
当某个数据集合只涉及在⼀端插⼊和删除数据，并且满⾜后进先出、先进后出的特性，我们就应该⾸选栈这种数据结构
不管是顺序栈还是链式栈，⼊栈、出栈只涉及栈顶个别数据的操作，所有时间复杂度都是 O(1)。栈是⼀种操作受限的数据结构，只⽀持⼊栈和出栈操作。后进先出是它最⼤的特点。栈既可以通过数组实现，也可以通过链表实现。
内存中的堆栈和数据结构中的堆栈不是⼀个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象出来的数据存储结构：
内存空间在逻辑上分为三部分：
代码区：存储⽅法体的⼆级制代码。⾼级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执⾏代码的却换；
静态数据区：存储全局变量、静态变量、常量，由系统⾃动分配和回收；
栈区：存储运⾏⽅法的形参、局部变量、返回值，由系统⾃动分配和回收；
堆区：new ⼀个对象的引⽤或地址存储在栈区，执⾏该对象存储在堆区中的真实数据。
09 队列
先进者先出
不管是顺序队列还是链式队列，主要的两个操作是⼊队和出队，最⼤特点是先进先出。
⼏种⾼级的队列结构：
阻塞队列（⽣产者-消费者问题）；
并发队列（多线程与原⼦锁操作）；
10 递归
递归需要满⾜的三个条件：
⼀个问题的解可以分解为⼏个⼦问题的解；
这个问题与分解之后的⼦问题，出来数据规模不同，求解思路完全⼀样；
存在递归终⽌条件；
如何编写递归代码？
递推公式
终⽌条件
缺点：
堆栈溢出
重复计算
函数调⽤耗时多
空间复杂度⾼
......
11&12 排序
常见排序算法：
是否基于⽐较
排序算法时间复杂度
时间复杂度是否基于⽐较
冒泡、插⼊、选择O(n2)是
快排、归并O(nlog n)是
桶、计数、基数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)
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是⼀个原地排序算法。
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素⼤⼩相等的时候，我们不做交换，相同⼤⼩的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
最好情况下，要排序的数据已经是有序的了，我们只需要进⾏⼀次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。⽽最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进⾏n次冒泡操作，所以最坏情况时间复杂度为O(n2)。
插⼊排序
插⼊算法的核⼼思想是取未排序区间中的元素，在已排序区间中到合适的插⼊位置将其插⼊，并保证已排序区间数据⼀直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
⽰例代码：
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)
从实现过程可以很明显地看出，插⼊排序算法的运⾏并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是⼀个原地排序算法。
在插⼊排序中，对于值相同的元素，我们可以选择将后⾯出现的元素，插⼊到前⾯出现元素的后⾯，这样就可以保持原有的前后顺序不变，所以插⼊排序是稳定的排序算法。
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组⾥⾯查
插⼊位置，每次只需要⽐较⼀个数据就能确定插⼊的位
置。所以这种情况下，最好是时间复杂度为O(n)。注意，这⾥是从尾到头遍历已经有序的数据。如果数组是倒序的，每次插⼊都相当于在数组的第⼀个位置插⼊新的数据，所以需要移动⼤量的数据，所以最坏情况时间复杂度为O(n2)。对于插⼊排序来说，每次插⼊操作都相当于在数组中插⼊⼀个数据，循环执⾏ n 次插⼊操作，所以平均时间复杂度为O(n2)。
选择排序
选择排序算法的实现思路有点类似插⼊排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中到最⼩的元素，将其放到已排序区间的末尾。
⽰例代码：
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(1)，是⼀种原地排序算法。
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。
选择排序每次都要剩余未排序元素中的最⼩值，并和前⾯的元素交换位置，这样破坏了稳定性。是⼀种不稳定的排序算法。
是否稳定最好最坏平均
是否原地排序是否稳定
是否原地排序
冒泡是是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:]
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)
性能分析：
是⼀个稳定的排序算法。
时间复杂度是O(nlog n)。
空间复杂度是O(n)。
快速排序
快排核⼼思想就是分治和分区。如果要排序数组中下标从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)
性能分析：
时间复杂度也是O(nlog n)。
但是，公式成⽴的前提是每次分区操作，我们选择的pivot都很合适，正好能将⼤区间对等地⼀分为⼆。但实际上这种情况是很难实现的
13 线性排序
桶排序
核⼼思想是将要排序的数据分到⼏个有序的桶⾥，每个桶⾥的数据再单独进⾏排序。桶内排完序之后，再把每个桶⾥的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序⽐较适合⽤在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量⽐较⼤，内存有限，⽆法将数据全部加载到内存中。
计数排序
计数排序其实是桶排序的⼀种特殊情况。当要排序的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]

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