计算机算法核心知识点整理个人精炼笔记面试刷题直接背目录第一章 绪论1.1 什么是算法1.2 算法的描述1.3 算法的分析1.4重要的问题类型第2章 算法效率分析基础第3章 蛮力法3.1 选择排序和冒泡排序3.1.1选择排序3.1.2 冒泡排序3.2 顺序查找和蛮力字符串匹配3.2.1 顺序查找3.2.2蛮力字符串匹配3.3 最近对和凸包问题的蛮力算法3.3.1 最近问题3.3.2 凸包问题3.4 穷举查找3.5深度优先查找和广度优先查找3.5.1 深度优先查找3.5.2 广度优先查找第4章 减治法4.1 插入排序4.2 拓扑排序4.3生成祝贺对象的算法4.4 减常因子算法4.4.1 折半查找4.4.2 假币问题4.4.3 俄式乘法4.4.4 约瑟夫斯问题4.5减可变规模算法4.5.1 插值查找第五章 分治法5.1 合并排序5.2 快速排序第一章 绪论1.1 什么是算法算法(algorithm)是一系列解决问题的明确指令也就是说对于符合一定规范的输入能够在有限时间内获得要求的输出。观点可以认为算法是问题的程序化解决方案。1.2 算法的描述伪代码(pseudocode)是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确而且用伪代码描述的算法往往会更简洁。用箭头代表赋值操作。1.3 算法的分析效率有两种时间效率(time efficiency),指出算法运行有多快。空间效率(space efficiency),说明算法需要多少额外的存储空间。1.4重要的问题类型排序问题(sorting problem)要求我们按照升序重新排列给定列表中的数据项。查找问题(searching problem)就是在给定的集合或者是多重集它允许多个元素具有相同的值)中找一个给定的值[我们称之为查找键(search key)]。字符串处理也称字符串匹配问题图问题组合问题几何问题类似于点、线、多面体这样的几何对象。数值问题(numerical problem)是另一个广阔的具体应用领域涉及具有连续性的数学问题像解方程和方程组计算定积分以及求函数的值等。第2章 算法效率分析基础不做笔记第3章 蛮力法蛮力法(brute force)是一种简单直接地解决问题的方法常常直接基于问题的描述和所涉及的概念定义。3.1 选择排序和冒泡排序3.1.1选择排序3.1.2 冒泡排序3.2 顺序查找和蛮力字符串匹配3.2.1 顺序查找该算法只是简单地将给定列表中的连续元素和给定的查找键进行比较直到遇到一个匹配的元素成功查找或者在遇到匹配元素前就遍历了整个列表失败查找)。实现顺序查找时常常会使用这样一个小技巧如果我们把查找键添加到列表的末尾那么查找就一定会成功所以不必在算法的每次循环时都检查是否到达了表的末尾。以下是这个增强版本的伪代码。3.2.2蛮力字符串匹配查找字符串第一个字符的位置请注意在这个例子中几乎每做一次字符比较就要移动一次模式的位置。然而最坏的情况比这还要糟得多在移动模式之前算法可能会做足m次比较而n-m1次尝试的每一次都可能会遇到这种情况。因此在最坏的情况下该算法属于O(nm)。3.3 最近对和凸包问题的蛮力算法3.3.1 最近问题最近点对问题要求在一个包含n个点的集合中找出距离最近的两个点。这种处理平面或者高维空间的邻近点的问题在各种计算几何问题当中是最简单的。最近点对问题的一个最重要的应用是统计学中的聚类分析。3.3.2 凸包问题在平面或者高维空间的一个给定点集合中寻找凸包被视为计算几何中最重要的问题之一。定义对于平面上的一个点集合有限的或无限的如果以集合中任意两点p和q为端点的线段都属于该集合我们说这个集合是凸的。凸包问题省略3.4 穷举查找对于组合问题来说穷举查找(exhaustive search)是一种简单的蛮力方法。它要求生成问题域中的每一个元素选出其中满足问题约束的元素然后再找出一个期望元素例如使目标函数达到最优的元素)。注意虽然穷举查找的思想很简单直接但在实现时它常常会要求算法来生成某些组合对象。常见问题旅行商问题背包问题分配问题3.5深度优先查找和广度优先查找3.5.1 深度优先查找深度优先查找可以从任意顶点开始访问图的顶点然后把该顶点标记为已访问。在每次迭代的时候该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点可以任意选择一个顶点。但在实际应用中选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。在我们的例子中我们总是根据顶点的字母顺序来选择顶点。)这个过程一直持续直到遇到一个终点一该顶点的所有邻接顶点都已被访问过。在该终点上该算法沿着来路后退一条边并试着继续从那里访问未访问的顶点。在后退到起始顶点并且起始顶点也是一个终点时该算法最终停了下来。这样起始顶点所在的连通分量的所有顶点都被访问过了。如果未访问过的顶点仍然存在该算法必须从其中任一顶点开始重复上述过程。用一个栈来跟踪深度优先查找的操作是比较方便的。在第一次访问一个顶点时也就是说开始对该顶点的访问时)我们把该顶点入栈当它成为一个终点时也就是说结束对该顶点的访问时)我们把它出栈。深度优先查找树depth-first search forest3.5.2 广度优先查找按照一种同心圆的方式首先访问所有和初始顶点邻接的顶点然后是离它两条边的所有未访问顶点以此类推直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点该算法必须从图的其他连通分量中的任意顶点重新开始。使用队列注意它和深度优先查找的区别来跟踪广度优先查找的操作是比较方便的。该队列先从遍历的初始顶点开始将该顶点标记为已访问。在每次迭代的时候该算法找出所有和队头顶点邻接的未访问顶点把它们标记为已访问再把它们入队。然后将队头顶点从队列中移去。广度优先查找森林breadth-first search forcest第4章 减治法4.1 插入排序我们考虑如何用减一技术对一个数组A[0.-1]排序。遵循该方法的思路我们假设对较小数组A[0.n-2]排序的问题已经解决了得到了一个大小为n-1的有序数组A0]≤…≤[n-2]。我们如何利用这个较小规模的解并将元素A[n-1]考虑进来来得到原问题的解呢显然我们需要做的就是在这些有序的元素中为A[-1]找到一个合适的位置然后把它插入到那里。一般来说我们可以从右到左扫描这个有序的子数组直到遇到第一个小于等于A[-1]的元素然后把A[n-1]插在该元素的后面。这种算法被称为直接插入排序(straight insertion sort),或者简称为插入排序(insertion sort)。4.2 拓扑排序4.3生成祝贺对象的算法4.4 减常因子算法以上略有时间再做笔记4.4.1 折半查找对于有序数组的查找来说折半查找是一种性能卓越的算法。它通过比较查找键K和数组中间元素A[m]来完成查找工作。如果它们相等算法结束。否则如果KA[m],就对数组的前半部分执行该操作如果KA[m],则对数组的后半部分执行该操作。4.4.2 假币问题4.4.3 俄式乘法4.4.4 约瑟夫斯问题 三问题略4.5减可变规模算法4.5.1 插值查找有时间再做笔记第五章 分治法基本思想将一个规模为n的问题分解为k个规模较小的子问题这些子问题互相独立且原问题相同。递归地解这些子问题然后将各子问题的解合并得到原问题的解。精髓分——将问题分解为规模更小的子问题。治——将这些规模更小的子问题逐个击破。合——将已解决的子问题合并最终得到原问题的解。5.1 合并排序图5.2演示的是用合并排序算法对数列8,3,2,9,7,1,5,4进行排序的操作过程。5.2 快速排序如何系统学习网络安全/黑客网络安全不是「速成黑客」而是守护数字世界的骑士修行。当你第一次用自己写的脚本检测出漏洞时那种创造的快乐远胜于电影里的炫技。装上虚拟机从配置第一个Linux环境开始脚踏实地从基础命令学起相信你一定能成为一名合格的黑客。如果你还不知道从何开始我自己整理的282G的网络安全教程可以分享我也是一路自学走过来的很清楚小白前期学习的痛楚你要是没有方向还没有好的资源根本学不到东西下面是我整理的网安资源希望能帮到你。需要的话可以V扫描下方二维码联系领取~如果二维码失效可以点击下方链接去拿一样的哦【CSDN大礼包】最新网络安全/网安技术资料包~282G无偿分享1.从0到进阶主流攻防技术视频教程包含红蓝对抗、CTF、HW等技术点2.入门必看攻防技术书籍pdf书面上的技术书籍确实太多了这些是我精选出来的还有很多不在图里3.安装包/源码主要攻防会涉及到的工具安装包和项目源码防止你看到这连基础的工具都还没有4.面试试题/经验网络安全岗位面试经验总结谁学技术不是为了赚$呢找个好的岗位很重要需要的话可以V扫描下方二维码联系领取~因篇幅有限资料较为敏感仅展示部分资料添加上方即可获取如果二维码失效可以点击下方链接去拿一样的哦【CSDN大礼包】最新网络安全/网安技术资料包~282G无偿分享
计算机算法核心知识点整理个人精炼笔记面试刷题直接背目录第一章 绪论1.1 什么是算法1.2 算法的描述1.3 算法的分析1.4重要的问题类型第2章 算法效率分析基础第3章 蛮力法3.1 选择排序和冒泡排序3.1.1选择排序3.1.2 冒泡排序3.2 顺序查找和蛮力字符串匹配3.2.1 顺序查找3.2.2蛮力字符串匹配3.3 最近对和凸包问题的蛮力算法3.3.1 最近问题3.3.2 凸包问题3.4 穷举查找3.5深度优先查找和广度优先查找3.5.1 深度优先查找3.5.2 广度优先查找第4章 减治法4.1 插入排序4.2 拓扑排序4.3生成祝贺对象的算法4.4 减常因子算法4.4.1 折半查找4.4.2 假币问题4.4.3 俄式乘法4.4.4 约瑟夫斯问题4.5减可变规模算法4.5.1 插值查找第五章 分治法5.1 合并排序5.2 快速排序第一章 绪论1.1 什么是算法算法(algorithm)是一系列解决问题的明确指令也就是说对于符合一定规范的输入能够在有限时间内获得要求的输出。观点可以认为算法是问题的程序化解决方案。1.2 算法的描述伪代码(pseudocode)是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确而且用伪代码描述的算法往往会更简洁。用箭头代表赋值操作。1.3 算法的分析效率有两种时间效率(time efficiency),指出算法运行有多快。空间效率(space efficiency),说明算法需要多少额外的存储空间。1.4重要的问题类型排序问题(sorting problem)要求我们按照升序重新排列给定列表中的数据项。查找问题(searching problem)就是在给定的集合或者是多重集它允许多个元素具有相同的值)中找一个给定的值[我们称之为查找键(search key)]。字符串处理也称字符串匹配问题图问题组合问题几何问题类似于点、线、多面体这样的几何对象。数值问题(numerical problem)是另一个广阔的具体应用领域涉及具有连续性的数学问题像解方程和方程组计算定积分以及求函数的值等。第2章 算法效率分析基础不做笔记第3章 蛮力法蛮力法(brute force)是一种简单直接地解决问题的方法常常直接基于问题的描述和所涉及的概念定义。3.1 选择排序和冒泡排序3.1.1选择排序3.1.2 冒泡排序3.2 顺序查找和蛮力字符串匹配3.2.1 顺序查找该算法只是简单地将给定列表中的连续元素和给定的查找键进行比较直到遇到一个匹配的元素成功查找或者在遇到匹配元素前就遍历了整个列表失败查找)。实现顺序查找时常常会使用这样一个小技巧如果我们把查找键添加到列表的末尾那么查找就一定会成功所以不必在算法的每次循环时都检查是否到达了表的末尾。以下是这个增强版本的伪代码。3.2.2蛮力字符串匹配查找字符串第一个字符的位置请注意在这个例子中几乎每做一次字符比较就要移动一次模式的位置。然而最坏的情况比这还要糟得多在移动模式之前算法可能会做足m次比较而n-m1次尝试的每一次都可能会遇到这种情况。因此在最坏的情况下该算法属于O(nm)。3.3 最近对和凸包问题的蛮力算法3.3.1 最近问题最近点对问题要求在一个包含n个点的集合中找出距离最近的两个点。这种处理平面或者高维空间的邻近点的问题在各种计算几何问题当中是最简单的。最近点对问题的一个最重要的应用是统计学中的聚类分析。3.3.2 凸包问题在平面或者高维空间的一个给定点集合中寻找凸包被视为计算几何中最重要的问题之一。定义对于平面上的一个点集合有限的或无限的如果以集合中任意两点p和q为端点的线段都属于该集合我们说这个集合是凸的。凸包问题省略3.4 穷举查找对于组合问题来说穷举查找(exhaustive search)是一种简单的蛮力方法。它要求生成问题域中的每一个元素选出其中满足问题约束的元素然后再找出一个期望元素例如使目标函数达到最优的元素)。注意虽然穷举查找的思想很简单直接但在实现时它常常会要求算法来生成某些组合对象。常见问题旅行商问题背包问题分配问题3.5深度优先查找和广度优先查找3.5.1 深度优先查找深度优先查找可以从任意顶点开始访问图的顶点然后把该顶点标记为已访问。在每次迭代的时候该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点可以任意选择一个顶点。但在实际应用中选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。在我们的例子中我们总是根据顶点的字母顺序来选择顶点。)这个过程一直持续直到遇到一个终点一该顶点的所有邻接顶点都已被访问过。在该终点上该算法沿着来路后退一条边并试着继续从那里访问未访问的顶点。在后退到起始顶点并且起始顶点也是一个终点时该算法最终停了下来。这样起始顶点所在的连通分量的所有顶点都被访问过了。如果未访问过的顶点仍然存在该算法必须从其中任一顶点开始重复上述过程。用一个栈来跟踪深度优先查找的操作是比较方便的。在第一次访问一个顶点时也就是说开始对该顶点的访问时)我们把该顶点入栈当它成为一个终点时也就是说结束对该顶点的访问时)我们把它出栈。深度优先查找树depth-first search forest3.5.2 广度优先查找按照一种同心圆的方式首先访问所有和初始顶点邻接的顶点然后是离它两条边的所有未访问顶点以此类推直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点该算法必须从图的其他连通分量中的任意顶点重新开始。使用队列注意它和深度优先查找的区别来跟踪广度优先查找的操作是比较方便的。该队列先从遍历的初始顶点开始将该顶点标记为已访问。在每次迭代的时候该算法找出所有和队头顶点邻接的未访问顶点把它们标记为已访问再把它们入队。然后将队头顶点从队列中移去。广度优先查找森林breadth-first search forcest第4章 减治法4.1 插入排序我们考虑如何用减一技术对一个数组A[0.-1]排序。遵循该方法的思路我们假设对较小数组A[0.n-2]排序的问题已经解决了得到了一个大小为n-1的有序数组A0]≤…≤[n-2]。我们如何利用这个较小规模的解并将元素A[n-1]考虑进来来得到原问题的解呢显然我们需要做的就是在这些有序的元素中为A[-1]找到一个合适的位置然后把它插入到那里。一般来说我们可以从右到左扫描这个有序的子数组直到遇到第一个小于等于A[-1]的元素然后把A[n-1]插在该元素的后面。这种算法被称为直接插入排序(straight insertion sort),或者简称为插入排序(insertion sort)。4.2 拓扑排序4.3生成祝贺对象的算法4.4 减常因子算法以上略有时间再做笔记4.4.1 折半查找对于有序数组的查找来说折半查找是一种性能卓越的算法。它通过比较查找键K和数组中间元素A[m]来完成查找工作。如果它们相等算法结束。否则如果KA[m],就对数组的前半部分执行该操作如果KA[m],则对数组的后半部分执行该操作。4.4.2 假币问题4.4.3 俄式乘法4.4.4 约瑟夫斯问题 三问题略4.5减可变规模算法4.5.1 插值查找有时间再做笔记第五章 分治法基本思想将一个规模为n的问题分解为k个规模较小的子问题这些子问题互相独立且原问题相同。递归地解这些子问题然后将各子问题的解合并得到原问题的解。精髓分——将问题分解为规模更小的子问题。治——将这些规模更小的子问题逐个击破。合——将已解决的子问题合并最终得到原问题的解。5.1 合并排序图5.2演示的是用合并排序算法对数列8,3,2,9,7,1,5,4进行排序的操作过程。5.2 快速排序如何系统学习网络安全/黑客网络安全不是「速成黑客」而是守护数字世界的骑士修行。当你第一次用自己写的脚本检测出漏洞时那种创造的快乐远胜于电影里的炫技。装上虚拟机从配置第一个Linux环境开始脚踏实地从基础命令学起相信你一定能成为一名合格的黑客。如果你还不知道从何开始我自己整理的282G的网络安全教程可以分享我也是一路自学走过来的很清楚小白前期学习的痛楚你要是没有方向还没有好的资源根本学不到东西下面是我整理的网安资源希望能帮到你。需要的话可以V扫描下方二维码联系领取~如果二维码失效可以点击下方链接去拿一样的哦【CSDN大礼包】最新网络安全/网安技术资料包~282G无偿分享1.从0到进阶主流攻防技术视频教程包含红蓝对抗、CTF、HW等技术点2.入门必看攻防技术书籍pdf书面上的技术书籍确实太多了这些是我精选出来的还有很多不在图里3.安装包/源码主要攻防会涉及到的工具安装包和项目源码防止你看到这连基础的工具都还没有4.面试试题/经验网络安全岗位面试经验总结谁学技术不是为了赚$呢找个好的岗位很重要需要的话可以V扫描下方二维码联系领取~因篇幅有限资料较为敏感仅展示部分资料添加上方即可获取如果二维码失效可以点击下方链接去拿一样的哦【CSDN大礼包】最新网络安全/网安技术资料包~282G无偿分享
