算法导论期末详细归纳总结(含习题和完整算法代码)

2024-07-17 15:33| 来源: 网络整理| 查看: 265

2021新年似旧年，第一篇牛年博客！

4号算法导论期末考试，这篇文章助各大学子期末冲刺高分

给大家推荐一个超牛逼的算法动态图网址： https://visualgo.net/zh

复习数据结构的小伙伴指路: 一起复习数据结构吧 (三) 含(栈、队列) https://editor.csdn.net/md/?articleId=112246422

一: 各种算法时间复杂度

(一) 排序算法:

直接插入排序: O( n 2 n^2 n2)、稳定shell排序: O( n 1.3 n^{1.3} n1.3）、不稳定归并排序: O(n l g n lgn lgn)、稳定堆排序: O(n l g n lgn lgn)、不稳定快速排序: O(n l g n lgn lgn)、不稳定基数排序: O(d( n + k n+k n+k))、稳定平方阶有: 直接选择排序、冒泡排序、直接插入排序；线性阶的有桶排序、基数排序、计数排序；稳定的有: 冒泡排序、归并排序、基数排序、直接插入排序不稳定的有: 选择排序、快速排序、希尔排序、堆排序

(二) 各大算法实例

最大子数组：T(n) = θ( n l g n nlgn nlgn)矩阵乘法的Strassen算法: T(n) = θ( n l g 7 n^{lg7} nlg7)广度优先搜索: O \Omicron O( V + E V+E V+E)最长特征序列的长度期望θ( l g n lgn lgn)生日悖论: θ( n \sqrt n n ) 二: 广度优先搜索( b f s bfs bfs) 大致思路: 从开始节点出发,遍历所有结点,通过队列这一数据结构实现入队出队操作，一直到找到最终结点时才执行回溯操作，最终路径列表里面的结点个数减去1则为最短路径!代码如下，建议先看完大致思路再看代码，最好自己能够debug走一遍 from collections import deque from collections import namedtuple # start_node: 开始节点 # end_node: 目标节点 # graph: 图字典 def bfs(start_node, end_node, graph): node = namedtuple('node', 'name, from_node') # 使用nametuple定义节点,用于存储前置节点 search_queue = deque() # 使用双端队列, 根据先进先出获取下一个遍历的节点 name_search = deque() # 存储队列中已有节点名称 visited = {} # 存储已访问过的节点 search_queue.append(node(start_node, None)) #填入初始节点, 从队列后面加入 name_search.append(start_node) # 存储已访问过的节点 path = [] # 回溯路径 path_len = 0 # 路径长度 print('开始搜索........') # 当搜索队列不为空则一直遍历下去 while search_queue: print('待遍历节点:', name_search) current_node = search_queue.popleft() # 从队列前边获取节点 name_search.popleft() # 将名称也相应弹出 if current_node.name not in visited: # 当前节点没有被访问过的话 print('当前节点: ', current_node.name, end=' | ') if current_node.name == end_node: # 找到目标节点 pre_node = current_node # 路径回溯的关键在于每个节点中存储的前置节点 while True: if pre_node.name == start_node: # 如果前置节点为当前节点 path.append(start_node) # 将当前节点加入路径,保证路径的完整性 break # 退出 else: path.append(pre_node.name) # 不断将前置节点名称加入路径 pre_node = visited[pre_node.from_node] # 取出前置节点的前置节点 path_len = len(path) - 1 break else: visited[current_node.name] = current_node # 没找到则将该节点设置为已访问 for node_name in graph[current_node.name]: # 遍历相邻节点 if node_name not in name_search: # 如果相邻节点不在搜索队列中 search_queue.append(node(node_name, current_node.name)) name_search.append(node_name) print(f'搜索完毕,最短路径为: {path[::-1]},"长度为:" {path_len}') if __name__ == '__main__': graph = dict() # 使用字典表示有向图 graph[1] = [3, 2] graph[2] = [5] graph[3] = [4, 7] graph[4] = [6] graph[5] = [6] graph[6] = [8] graph[7] = [8] graph[8] = [] bfs(1, 8, graph) python代码实现广度优先搜索结果如下所示:

三: 先序，中序，后序遍历结果先序遍历: 根、左子树、右子树中序遍历: 左子树、根、右子树后序遍历: 左子树、右子树、根

1: 已知先序为ABCDEFGH、中序为BDCEAFHG, 求后序

在这里插入图片描述

首先根据先序和中序画出二叉树的图形第一步通过先序找根节点: A, 再去中序中找到A的位置，A左边的序列BDCE为左子树，A右边的序列FHG为右子树先从中序看左子树BDCE，先序中BDCE中最先出现的则为根结点,B结点最先出现，因此B结点左子树为空,右子树为DCE；在从先序中看C最先出现则为根结点，C左边的D为左子树，右边的E为右子树,画出如上图所示的左子树再从中序看右子树FHG，先序中最先出现的是F，因此F为根节点，左子树为空，右子树为HG；先序中G比H先出现，所以G为根节点，H为G的左孩子，再画出右子树，整颗二叉树就画出来如上图所示啦!最后根据如图所示的二叉树写出后序遍历序列,大致遍历思路如下:首先后序遍历是先访问左子树再访问右子树，最后访问根节点；所以从根节点A开始访问左子树，找到结点B，再访问B的左子树为空，接着再访问B的右子树，找到根节点C，再访问C的左子树，找到结点D，再访问D的左子树为空，访问D的右子树也为空，最后输出根节点D；然后再访问C的右子树E，E的左子树为空，右子树也为空，最后输出结点E；C的左子树访问完毕，右子树访问完毕，接着打印输出结点C；B的左子树访问完毕，右子树访问完毕，接着打印结点B，然后A的左子树访问完毕，开始访问A的右子树；先找到节点F，访问其左子树为空，再访问其右子树，找到结点G，访问其左子树，找到结点H，其左右孩子皆为空，因此打印输出H，然后访问结点G的右孩子即右子树为空，当左右孩子都访问完毕，打印输出结点G，接着F的右子树访问完毕，再打印结点F，A的右子树访问完毕，最后输出结点A，最终的后序遍历的序列为: DECBHGFA

如果已知中序和后序，大致思路与上述类似，只是后序中后出现的结点为根节点

四: 插入排序代码分析夜斗小神社代表人凌晨肝算法，雅哈咖啡是真的顶，现在当地时间为: 在这里插入图片描述

插入排序的python代码如下所示: def insert_sort(list): for i in range(1, len(list): # i从第二个元素开始 temp = list[i] # 将要插入的值赋给temp j = i - 1 # j为i位置后一个(如果i指向第二个，则j就是第一个) # 如果j非负,且j对应的值大于temp while(j>=0) & (list[j] > temp) # ps: 这里和步骤需要自己动手画图更容易理解下面两行代码意思 # 大致意思是将元素进行后移，留下一个空位能被temp插入 list[j+1] = list[j] j = j - 1 list[j+1] = temp # 将temp的值插入下面是一个我录制的插入排序的动态图，建议反复食用，没有vip就有水印难受！在这里插入图片描述

五: 归并排序代码分析

在这里插入图片描述

雅哈咖啡真的牛，睡意全无，贴张昨天看小库里比赛时的截图!! # 归并排序python代码 def MergeSort(lists): if len(lists) //行循环 int j = r+i-1;//列的控制 //找m[i][j]的最小值，先初始化一下，令k=i m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; //k从i+1到j-1循环找m[i][j]的最小值 for(int k = i+1;k m[i][j]=temp; //s[][]用来记录在子序列i-j段中，在k位置处断开能得到最优解 s[i][j]=k; } } } }

在这里插入图片描述详细了解矩阵链乘法可以参考这篇博客https://www.cnblogs.com/crx234/p/5988453.html

十二: 最长公共子序列核心思想: 查找A、B两个序列公共相同的最长子序列例如a = ‘ABCBDAB’，b = ‘BDCABA’，最长公共子序列: BCBA尽管个数不是唯一的,可能会有两个以上, 但是长度一定是唯一有些时候，动态规划其中的子问题很复杂，不要被弄得迷茫了 def lcs(a, b): lena = len(a) # a序列的长度 lenb = len(b) # b序列的长度 c = [[0 for i in range(lenb + 1)] for j in range(lena + 1)] # 存放两个列表最长公共子序列的长度 flag = [[0 for i in range(lenb + 1)] for j in range(lena + 1)] # 帮助构造最优解 # 首先由左至右计算c的第一行, 然后计算第二行，以此类推 for i in range(lena): for j in range(lenb): if a[i] == b[j]: # 如果a[i]等于b[j]是LCS的一个元素 # 因为第一行与第一列位构造的表头都是0, 因此i+1,j+1,从第二行第二列那个0开始算 c[i+1][j+1] = c[i][j] + 1 flag[i+1][j+1] = 'ok' # flag位置显示ok，是LCS中的一个元素 elif c[i+1][j] > c[i][j+1]: # 如果c表中LCS中记录的长度,当左边的值大于其上方的值 c[i+1][j+1] = c[i+1][j] # 将左边的LCS长度的值赋值给当前位置 flag[i+1][j+1] = 'left' # 箭头号指向左边，表示从左边赋值来的 else: c[i+1][j+1] = c[i][j+1] # 如果c表中LCS中记录的长度,当上边的值大于其左边的值 flag[i+1][j+1] = 'up' # 箭头号指向上方up，表示从上边继承下来的 return c, flag def printLcs(flag, a, i, j): if i == 0 or j == 0: return if flag[i][j] == 'ok': printLcs(flag, a, i - 1, j - 1) print(a[i - 1], end='') elif flag[i][j] == 'left': printLcs(flag, a, i, j - 1) else: printLcs(flag, a, i - 1, j) a = 'ABCBDAB' b = 'BDCABA' c, flag = lcs(a, b) for i in c: print(i) print('') for j in flag: print(j) print('') printLcs(flag, a, len(a), len(b)) print('') ''' 最终结果: [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1] [0, 1, 1, 1, 1, 2, 2] [0, 1, 1, 2, 2, 2, 2] [0, 1, 1, 2, 2, 3, 3] [0, 1, 2, 2, 2, 3, 3] [0, 1, 2, 2, 3, 3, 4] [0, 1, 2, 2, 3, 4, 4] [0, 0, 0, 0, 0, 0, 0] [0, 'up', 'up', 'up', 'ok', 'left', 'ok'] [0, 'ok', 'left', 'left', 'up', 'ok', 'left'] [0, 'up', 'up', 'ok', 'left', 'up', 'up'] [0, 'ok', 'up', 'up', 'up', 'ok', 'left'] [0, 'up', 'ok', 'up', 'up', 'up', 'up'] [0, 'up', 'up', 'up', 'ok', 'up', 'ok'] [0, 'ok', 'up', 'up', 'up', 'ok', 'up'] BCBA Process finished with exit code 0 '''

我去旅行，是因为我决定了要去，并不是因为对风景的兴趣

不惋惜，不呼唤，我也不啼哭。一切将逝去，如苹果花丛的薄雾。金黄的落叶堆满心间，我已不再是青春少年胆小鬼连幸福都会害怕，碰到棉花都会受伤，有时还被幸福所伤从卖气球的人那里，每个孩子牵走一个心愿，祝大家在新的一年里好运连连，万事顺遂！热爱、可抵岁月漫长！

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章