企业标志,南昌seo外包公司,青岛集团网站建设,江西 网站 建设 开发算法简介简单查找二分查找法 选择排序内存的工作原理数组和链表数组选择排序小结 递归小梗 要想学会递归#xff0c;首先要学会递归。 递归的基线条件和递归条件递归和栈小结 快速排序分而治之快速排序合并排序时间复杂度的平均情况和最糟情况小结 散列表散列函数缓冲小结性能… 算法简介简单查找二分查找法 选择排序内存的工作原理数组和链表数组选择排序小结 递归小梗 要想学会递归首先要学会递归。 递归的基线条件和递归条件递归和栈小结 快速排序分而治之快速排序合并排序时间复杂度的平均情况和最糟情况小结 散列表散列函数缓冲小结性能装填因子良好的哈希函数 特性小结 广度优先搜索图广度优先遍历查找最短路径队列小结 狄克斯特拉算法什么是狄克斯特拉算法什么时候使用狄克斯特拉算法术语负权边小结 贪婪算法教师调度问题背包问题集合覆盖问题近似算法NP完全问题如何识别np完全问题小结 动态规划背包问题简单算法动态规划动态规划问题处理商品一部分可以吗最长公共子串小结 k最近邻算法什么是回归机器学习垃圾邮件过滤器 next树二叉树 什么是反向索引傅里叶变换并行变换mapreduce映射函数归并函数布隆过滤器和HyperLogLogsha算法比较函数和sha函数检查密码和sha算法局部敏感的散列函数Diffie-Hellman密钥交换线性规划 算法简介
算法是一组完成任务的指令。算法与编程语言无关算法是一种思考。
简单查找
简单查找Simple Search也称为线性查找Linear Search是一种基本的查找算法适用于未排序或部分排序的数组。其基本思想是逐个地对数组元素进行比较直到找到目标元素或遍历完整个数组为止。
简单查找的实现非常直观通常用于简单的问题或者对性能要求不高的场景。然而它的时间复杂度为 O(n)其中 n 是数组的长度即在最坏情况下需要遍历整个数组才能确定目标元素的位置效率较低。
二分查找法
二分查找Binary Search是一种在有序数组中查找特定元素的搜索算法。它的基本思想是通过不断将待查找区间分成两半并利用目标值与中间元素的比较结果来确定下一步查找的区间直到找到目标值或者区间缩小到空为止。
二分查找适用于满足以下条件的场景 有序数组 数组必须是有序的升序或降序否则无法利用二分查找的特性。 静态数据结构 二分查找适用于静态的数据结构即查找操作频率远远大于插入、删除操作的场景。因为每次插入、删除操作都需要对数组进行调整破坏了数组的有序性。 连续存储空间 二分查找通常使用数组这种连续存储空间实现不适用于链式存储结构。 单调性 如果数组中存在重复元素只能找到其中一个元素的位置。另外二分查找通常是找到第一个满足条件的元素如果要找最后一个元素则需要稍作修改。
时间复杂度为 O(log n)效率较高。 你的目标是以最少的次数猜到这个数字。你每次猜测后我会说小了、大了或对了。
假设你从1开始依次往上猜猜测过程会是这样。 但这种方式是连续的询问方法比较笨。
可以一次排除一半增加效率 大了那余下的数字又排除了一半使用二分查找时你猜测的是中间的数字从而每次都 将余下的数字排除一半。接下来你猜6350和75中间的数字
仅当列表是有序的时候二分查找才管用。例如电话簿中的名字是按字母顺序排列的 因此可以使用二分查找来查找名字。如果名字不是按顺序排列的结果将如何呢
线性时间 是指算法的运行时间与输入规模成正比即随着输入规模的增加算法的执行时间也按比例增加。具体来说如果算法的运行时间是输入规模的线性函数我们就说该算法是线性时间的。
大O表示法是一种特殊的表示法指出了算法的速度有多快。 随着元素数量的增加二分查找需要的额外时间并不多而简单查找需要的额外时间却很多。因此随着列表的增长二分查找的速度比简单查找快得多。
大O表示法指出了算法有多快。大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数它指出了算法运行时间的增速。
除最糟情况下的运行时间外还应考虑平均情况的运行时间这很重要。
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。 O(log n)也叫对数时间这样的算法包括二分查找。 O(n)也叫线性时间这样的算法包括简单查找。 O(n * log n)这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n2)这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!)这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。 启示 算法的速度指的并非时间而是操作数的增速。 谈论算法的速度时我们说的是随着输入的增加其运行时间将以什么样的速度增加。 算法的运行时间用大O表示法表示。 O(log n)比O(n)快当需要搜索的元素越多时前者比后者快得越多
上图的O(n!)的例子
时间复杂度为 O(n!) 的算法通常用于解决排列组合等问题其运行时间随着输入规模的增加呈阶乘增长。这种算法在实际应用中一般不可接受因为它的运行时间增长速度太快对于稍微大一点的输入规模就会耗费非常大的时间。
一个简单的例子是求解 n 个元素的全排列。全排列是指将 n 个元素按照不同顺序排列的所有可能结果。一个简单的递归算法可以求解全排列其时间复杂度为 O(n!)因为对于 n 个元素第一个位置有 n 种选择第二个位置有 n-1 种选择以此类推总共有 n! 种排列。
小结 二分查找的速度比简单查找快得多。 O(log n)比O(n)快。需要搜索的元素越多前者比后者就快得越多。 算法运行时间并不以秒为单位。 算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示
选择排序
内存的工作原理 每个数据需要每个空间存放。
数组和链表
链表 链表的每个元素都存储了下一个元素的地址从而使一系列随机的内存地址串在一起。使用链表时根本就不需要移动元素。
链表Linked List 是一种常见的数据结构用于存储一系列元素。它由一系列节点Node组成每个节点包含数据和指向下一个节点的指针或引用。链表中的每个节点都有一个指针指向下一个节点最后一个节点的指针指向空值NULL表示链表的末尾。
链表与数组不同链表中的元素在内存中不必是连续存储的每个节点都可以独立存在于内存的任何位置。这使得链表具有动态分配内存的能力可以根据需要灵活地添加或删除节点而不需要像数组一样预先分配固定大小的内存空间。
链表通常分为单向链表、双向链表和循环链表等不同类型。其中单向链表中每个节点只有一个指针指向下一个节点双向链表中每个节点有两个指针分别指向前一个节点和后一个节点循环链表是一种特殊的链表其中最后一个节点的指针指向第一个节点形成一个循环。
链表在某些情况下比数组更加适用特别是在需要频繁插入和删除元素的情况下。但是链表的随机访问效率较低因为需要从头开始遍历链表才能找到指定位置的元素。
数组
数组Array是一种线性数据结构用于存储相同类型的元素序列。数组中的元素在内存中是连续存储的通过索引index可以访问数组中的元素。数组的长度是固定的一旦创建就无法改变。
数组通常由以下几个要素组成
元素类型数组中所有元素的数据类型必须相同例如整数数组、字符数组等。数组名数组的名称用于标识数组可以通过数组名来访问数组中的元素。元素个数数组中包含的元素数量即数组的长度。索引用于访问数组中特定位置元素的整数值。数组的索引从0开始因此第一个元素的索引为0第二个元素的索引为1依此类推。
数组的优点是能够快速访问任意位置的元素因为元素在内存中是连续存储的同时由于数组的长度固定所以可以在编译时静态地分配内存不需要动态分配和释放内存从而节省了内存管理的开销。
然而数组的缺点是长度固定无法动态调整大小插入和删除元素比较麻烦需要移动其他元素。因此在需要频繁插入和删除操作的情况下使用链表等数据结构可能更合适。
数组的元素带编号编号从0而不是1开始。例如在下面的数组中元素20的位置为1。元素的位置称为索引。 链表擅长插入和删除而数组擅长随机访问。
选择排序
选择排序Selection Sort是一种简单直观的排序算法。它的基本思想是每次从未排序的部分选取最小或最大的元素然后将其与未排序部分的第一个元素交换位置直到所有元素都排序完毕。
具体步骤如下
从待排序序列中找到最小或最大的元素将其与第一个元素交换位置。在剩余未排序的序列中找到最小或最大的元素将其与第二个元素交换位置。重复上述步骤直到所有元素都排序完毕。
选择排序的时间复杂度为 O(n^2)其中 n 是待排序序列的长度。虽然选择排序在时间复杂度上并不是最优的但由于其简单直观的实现方式在某些情况下仍然是一种有效的排序算法。 选择排序是一种灵巧的算法但其速度不是很快。
小结
计算机内存犹如一大堆抽屉。 需要存储多个元素时可使用数组或链表。 数组的元素都在一起。 链表的元素是分开的其中每个元素都存储了下一个元素的地址。 数组的读取速度很快。 链表的插入和删除速度很快。 在同一个数组中所有元素的类型都必须相同都为int、double等
递归
小梗 要想学会递归首先要学会递归。 递归是一种在函数定义中使用函数自身的编程技巧。简单来说递归是将一个问题分解成更小、更简单的子问题来解决直到问题被简化到最小规模的情况然后再逐步将结果合并起来。递归通常涉及到两个重要的概念基本情况和递归情况。
递归的基线条件和递归条件
由于递归函数调用自己因此编写这样的函数时很容易出错进而导致无限循环。
递归的条件包括两个重要部分基本情况和递归情况。 基本情况Base Case基本情况是递归算法中的终止条件它定义了递归应该在何时结束。当问题被简化到足够小或特定情况时递归将不再继续而是返回一个明确的值或执行某些特定操作。没有正确定义基本情况会导致无限递归最终导致栈溢出等问题。 递归情况Recursive Case递归情况定义了如何将原始问题分解为更小、更简单的子问题。在递归情况下递归函数会调用自身来解决子问题直到达到基本情况。
递归算法的关键是确保在每次递归调用时问题都能朝着基本情况靠近最终达到终止条件。否则递归会无限循环或无法终止。因此设计递归算法时需要仔细考虑如何将问题分解并定义明确的基本情况。
递归和栈
调用栈Call Stack是一种用于管理函数调用和返回的数据结构它在计算机内存中占据一块区域。当一个函数被调用时该函数的信息如参数、局部变量、返回地址等会被压入调用栈中然后函数开始执行。当函数执行完毕后它的信息会从调用栈中弹出控制权返回到调用该函数的地方。
递归与调用栈的关系密切因为递归函数在执行过程中会多次调用自身。每次递归调用都会将函数的信息压入调用栈中包括参数、局部变量和返回地址等。当递归达到基本情况时开始返回逐步弹出调用栈中的信息直到回到最初的调用位置。
递归的实现依赖于调用栈的支持它使得递归函数能够正确地返回到上一层调用同时保持每个递归调用之间的独立性。然而如果递归深度过大调用栈可能会耗尽内存导致栈溢出的错误。因此在设计递归算法时需要注意控制递归深度避免出现过深的递归调用。 使用栈虽然很方便但是也要付出代价存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存如果栈很高就意味着计算机存储了大量函数调用的信息。在这种情况 下你有两种选择。 重新编写代码转而使用循环。 使用尾递归。这是一个高级递归主题。另外并非所有的语言都支持尾递归 尾递归是指在递归函数的最后一步调用中递归调用是整个函数体的最后一条语句。在尾递归中递归调用的返回值直接被当前函数返回而不需要进行其他计算或操作。这种特殊的递归形式可以被优化为迭代从而减少调用栈的深度提高性能和节省内存。 尾递归的优化原理是重用当前栈帧而不是创建新的栈帧。在每次递归调用中函数参数和局部变量的值会被更新然后直接跳转到函数开头重新执行而不是在调用栈中创建新的栈帧。这样可以避免调用栈的不断增长节省了空间和时间。 小结
递归指的是调用自己的函数。 每个递归函数都有两个条件基线条件和递归条件。 栈有两种操作压入和弹出。 所有函数调用都进入调用栈。 调用栈可能很长这将占用大量的内存。
快速排序
分而治之
分治法Divide and ConquerDC是一种解决问题的思想和算法范式它将一个大问题分解成多个相似的小问题然后递归地解决这些小问题并将它们的解合并起来得到原问题的解。分治法通常包括三个步骤 分解Divide将原问题分解成若干个规模较小的子问题这些子问题是原问题的规模的一个子集。 解决Conquer递归地解决这些子问题。如果子问题的规模足够小并且可以直接求解则不再递归直接求解。 合并Combine将子问题的解合并成原问题的解。
分治法常用于解决具有以下特点的问题
原问题可以分解成规模较小的相似子问题。子问题可以独立求解且子问题的解可以合并成原问题的解。使用分治法求解的问题递归求解的复杂度通常可以表示为递归深度乘以每层的复杂度。
分治法的经典应用包括归并排序、快速排序和二分查找等。
快速排序
快速排序是一种常用的排序算法比选择排序快得多。例如C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了DC
**快速排序Quick Sort**是一种高效的排序算法它采用了分治法的思想。快速排序的基本思想是选择一个基准元素将数组分成两部分使得左边的元素都小于基准元素右边的元素都大于基准元素然后对左右两部分递归地进行排序最终得到一个有序数组。
具体步骤如下 选择基准元素从数组中选择一个基准元素通常选择第一个元素、最后一个元素或者中间元素。 分区操作将数组中小于基准元素的元素放到基准元素的左边大于基准元素的元素放到基准元素的右边基准元素放到合适的位置这个操作称为分区Partition操作。 递归排序对基准元素左边的子数组和右边的子数组分别递归地进行快速排序。 合并结果不需要合并因为在分区操作中数组已经被分成了两部分左边的部分都小于基准元素右边的部分都大于基准元素。
快速排序的时间复杂度为 O(nlogn)其中 n 为数组的大小。在平均情况下快速排序是一种性能较好的排序算法但在最坏情况下例如已排序的数组作为输入时间复杂度为 O(n^2)因此在实际应用中需要注意选择合适的基准元素来避免最坏情况的发生。
快速排序是一种高效的排序算法它的基本思想是选择一个基准元素通过一趟排序将待排序的记录分割成独立的两部分其中一部分记录的关键字均比基准元素小另一部分记录的关键字均比基准元素大然后分别对这两部分记录继续进行排序从而达到整个序列有序的目的。
快速排序的步骤如下
选择一个基准元素通常选择第一个元素、最后一个元素或者中间元素。使用两个指针一个指向数组的起始位置一个指向数组的末尾。从末尾开始找到第一个小于基准元素的元素从起始位置开始找到第一个大于基准元素的元素然后交换这两个元素。继续进行步骤 3直到两个指针相遇。将基准元素与相遇位置的元素交换使得基准元素左边的元素都小于它右边的元素都大于它。递归地对基准元素左边和右边的子数组进行排序。
快速排序的时间复杂度为 O(nlogn)在最坏情况下为 O(n^2)例如当序列已经有序时。快速排序是一种原地排序算法不需要额外的空间来存储临时数据但是它不是稳定的排序算法相同元素的相对位置可能会发生变化。
合并排序
合并排序Merge Sort是一种经典的分治算法它将一个待排序的数组分成两个子数组分别对这两个子数组进行排序然后将排好序的子数组合并成一个有序数组。具体步骤如下 分解Divide将待排序的数组分成两个长度大致相等的子数组。 解决Conquer递归地对两个子数组进行排序。 合并Merge将排好序的两个子数组合并成一个有序数组。 合并排序的时间复杂度合并排序的时间复杂度是 O(nlogn)其中 n 是待排序数组的长度。合并排序的空间复杂度是 O(n)因为在排序过程中需要一个与原数组长度相同的辅助数组来存储排序结果。 稳定性合并排序是一种稳定的排序算法即相同元素的相对位置在排序前后不发生改变。 优点合并排序的主要优点是稳定且时间复杂度稳定在 O(nlogn)在处理大数据量的排序时表现较好。 缺点合并排序的缺点是需要额外的内存空间来存储辅助数组因此对于内存空间较小的情况可能不太适用。
时间复杂度的平均情况和最糟情况
快速排序的时间复杂度取决于选取的基准元素不同的基准元素选择策略会导致不同的性能表现。一般情况下快速排序的时间复杂度为 O(nlogn)其中 n 是待排序数组的长度。但在最坏情况下快速排序的时间复杂度会退化到 O(n^2)这种情况通常发生在选取的基准元素不合适的情况下比如待排序数组已经有序或基本有序的情况下。在最好情况下即每次都能选取中间位置的元素作为基准元素时快速排序的时间复杂度为 O(nlogn)。
具体来说快速排序的平均时间复杂度为 O(nlogn)这是因为在平均情况下快速排序会将待排序数组均匀地分成两部分每次递归都会减少一半的元素数量因此总的比较次数是 O(nlogn)。但在最坏情况下比如每次选择的基准元素都是最大或最小的元素导致每次只能将待排序数组减少一个元素总的比较次数将是 O(n^2)。
为了避免快速排序的最坏情况通常可以采用随机化的方法来选择基准元素或者使用三数取中法等策略来选择基准元素这样可以尽可能地降低出现最坏情况的概率从而提高快速排序的性能。
小结
DC将问题逐步分解。使用DC处理列表时基线条件很可能是空数组或只包含一个元素的数组。 实现快速排序时请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。 大O表示法中的常量有时候事关重大这就是快速排序比合并排序快的原因所在。 比较简单查找和二分查找时常量几乎无关紧要因为列表很长时O(logn)的速度比O(n)快得多。
散列表
二分查找的速度非常快。但某些时刻还是需要更快的方式
散列函数
散列函数是这样的函数即无论你给它什么数据它都还你一个数字。 如果用专业术语来表达的话我们会说散列函数“将输入映射到数字”。你可能认为散列函数输出的数字没什么规律但其实散列函数必须满足一些要求。 它必须是一致的。例如假设你输入apple时得到的是4那么每次输入apple时得到的都必须为4。如果不是这样散列表将毫无用处。 它应将不同的输入映射到不同的数字。例如如果一个散列函数不管输入是什么都返回1它就不是好的散列函数。最理想的情况是将不同的输入映射到不同的数字。
散列函数准确地指出了价格的存储位置你根本不用查找之所以能够这样具体原因如下。 散列函数总是将同样的输入映射到相同的索引。每次你输入avocado得到的都是同一个数字。因此你可首先使用它来确定将鳄梨的价格存储在什么地方并在以后使用它来确定鳄梨的价格存储在什么地方。 散列函数将不同的输入映射到不同的索引。avocado映射到索引4milk映射到索引0。每种商品都映射到数组的不同位置让你能够将其价格存储到这里。 散列函数知道数组有多大只返回有效的索引。如果数组包含5个元素散列函数就不会返回无效索引100
散列函数Hash Function是一种将输入映射到固定大小范围的输出的函数。它通常用于将大量的数据映射到一个较小的数据集中例如将任意长度的消息映射到固定长度的散列值。散列函数的设计要求输出值的分布均匀即不同输入应该尽可能地映射到不同的输出值以减少冲突多个不同的输入映射到同一个输出值的发生。
散列函数在计算机科学中有广泛的应用例如在散列表Hash Table、密码学中的消息摘要算法如SHA-256、MD5等领域。在散列表中散列函数将键Key映射到数组的索引位置以实现高效的查找、插入和删除操作。
一个好的散列函数应该具备以下特性
一致性相同的输入应该映射到相同的输出。均匀性不同的输入应该均匀地映射到输出空间的不同位置减少冲突的发生。简单性散列函数的计算速度应该快不会成为程序的性能瓶颈。抗碰撞性难以找到两个不同的输入使得它们的散列值相同。
常见的散列函数包括简单的取余法、乘法散列法、位运算散列法等。选择合适的散列函数取决于具体的应用场景和数据特性。
防止碰撞是散列函数设计中的重要考虑因素碰撞指的是不同的输入映射到相同的散列值的情况。以下是几种常见的防碰撞方法 良好的散列函数设计一个好的散列函数应该尽可能均匀地将输入映射到输出空间减少碰撞的发生。良好的散列函数通常考虑到输入数据的特性并结合一些常见的技巧如乘法散列法、位运算散列法等。 开放定址法当发生碰撞时使用开放定址法来解决。开放定址法会尝试寻找散列表中的下一个空槽来存放冲突的元素直到找到空槽为止。常见的开放定址法包括线性探测、二次探测、双重散列等。 链地址法将散列值相同的元素存放在同一个链表中每个链表称为一个桶。当发生碰撞时将新元素插入到对应的链表中。链地址法可以有效地解决碰撞问题但可能会导致空间浪费。 再散列当发生碰撞时使用另一个散列函数再次对冲突元素进行散列直到找到空槽为止。再散列需要谨慎选择散列函数以避免再次发生碰撞。 建立完全二叉树将冲突的元素存储在一个完全二叉树中每个节点对应一个槽。当发生碰撞时沿着二叉树向下查找空槽存放冲突元素。完全二叉树方法可以保证在最坏情况下的时间复杂度为 O(log n)但实现较为复杂。 二次聚类法将哈希表划分为若干个聚类当发生冲突时首先在相应的聚类内进行查找提高查找效率。
缓冲
缓冲是一种常见的加速手段用于提高数据访问的效率。在计算机系统中缓冲主要分为硬件缓冲和软件缓冲两种类型。 硬件缓冲硬件缓冲通常指的是位于CPU和主存储器之间的高速缓存。CPU可以在高速缓存中存储最常用的数据和指令以减少对主存的访问次数提高数据访问速度。硬件缓冲的大小通常较小但速度非常快可以显著提高程序的性能。 软件缓冲软件缓冲是指应用程序在内存中维护的数据结构用于临时存储数据。软件缓冲可以减少对磁盘或网络的访问次数从而提高数据读写的效率。常见的软件缓冲包括文件缓冲、网络缓冲等。
缓冲作为加速的手段具有以下优点
降低访问延迟缓冲可以将数据预先加载到高速存储器中减少后续访问的延迟。降低对原始数据源的访问次数缓冲可以减少对原始数据源如磁盘、网络的频繁访问减轻数据源的负载。提高数据访问效率通过缓冲可以使数据更容易被访问从而提高数据访问的效率和性能。
然而缓冲也存在一些缺点例如可能导致数据不一致性、需要占用额外的内存等。因此在设计缓冲时需要综合考虑各种因素以达到最佳的性能和可靠性。
小结
这里总结一下散列表适合用于 模拟映射关系 防止重复 缓存/记住数据以免服务器再通过处理来生成它们。
性能
线性时间 对数时间 常量时间 装填因子
装填因子是指哈希表中已经存储的关键字数和哈希表长度的比值通常用 λ 表示。计算装填因子的公式如下 装填因子的大小直接影响到哈希表的性能。通常情况下装填因子过大会导致哈希冲突的概率增加从而影响查询效率而装填因子过小则会导致哈希表空间的浪费。通常情况下装填因子的建议取值范围为 0.5 到 0.8 之间。
良好的哈希函数 特性
良好的哈希函数具有以下特性 均匀性良好的哈希函数应该能够将关键字均匀地分布到哈希表的各个位置避免出现簇集现象即避免发生大量的哈希冲突。 简单性哈希函数应该简单易实现计算速度快不要过于复杂。 低碰撞率哈希函数应该使得碰撞的概率尽可能地低以提高查询效率。 高效性哈希函数的计算过程应该尽量高效不要消耗过多的计算资源。 均匀性哈希函数应该使得关键字的哈希值分布均匀避免出现簇集现象即使得每个桶中的关键字数量尽量相等。 唯一性不同的关键字应该具有不同的哈希值避免出现哈希冲突。
设计一个良好的哈希函数需要根据具体的应用场景和需求来选择通常需要综合考虑上述各个方面的因素。
小结
散列表是一种功能强大的数据结构其操作速度快还能让你以不同的方式建立数据模型。你可能很快会发现自己经常在使用它。 你可以结合散列函数和数组来创建散列表。 冲突很糟糕你应使用可以最大限度减少冲突的散列函数。 散列表的查找、插入和删除速度都非常快。 散列表适合用于模拟映射关系。 一旦填装因子超过0.7就该调整散列表的长度。 散列表可用于缓存数据例如在Web服务器上。 散列表非常适合用于防止重复
广度优先搜索 前往金门大桥这种问题被称为最短路径问题shorterst-path problem。 解决最短路径问题的算法被称为广度优先搜索
要确定如何从双子峰前往金门大桥需要两个步骤。 (1) 使用图来建立问题模型。 (2) 使用广度优先搜索解决问题。
图
图是由节点顶点和连接这些节点的边或弧组成的一种数据结构。图常用于表示多对多的关系比如网络中的路由关系、社交网络中的用户关系等。图可以分为有向图和无向图两种类型。 有向图Directed Graph图中的边有方向表示节点之间的单向关系。例如A-B 表示节点 A 指向节点 B。 无向图Undirected Graph图中的边没有方向表示节点之间的双向关系。例如A-B 表示节点 A 与节点 B 之间有连接。
图可以用多种方式来表示常见的有邻接矩阵和邻接表两种形式 邻接矩阵Adjacency Matrix使用二维数组来表示图中节点之间的关系如果节点 i 与节点 j 之间有边则 matrix[i][j] 1否则为 0。邻接矩阵适用于稠密图。 邻接表Adjacency List使用链表或数组的形式来表示图中每个节点的邻居节点。邻接表适用于稀疏图。
图在计算机科学中有广泛的应用比如在网络路由、社交网络分析、数据压缩等领域都有着重要的作用。
广度优先遍历
广度优先搜索Breadth First Search简称BFS 是一种用于图的遍历和搜索的算法。它从图中的一个特定顶点开始首先访问这个顶点然后依次访问该顶点的所有相邻顶点接着再依次访问这些相邻顶点的未被访问过的相邻顶点以此类推直到所有顶点都被访问过为止。
BFS通常使用队列来辅助实现。具体步骤如下
将起始顶点放入队列中并标记为已访问。从队列中取出一个顶点访问该顶点的所有未被访问过的相邻顶点并将这些相邻顶点放入队列中并标记为已访问。重复步骤2直到队列为空。
BFS的关键特点是以层次化的顺序逐层访问图中的顶点即先访问距离起始顶点最近的顶点然后是距离起始顶点为2的顶点依此类推。因此BFS常被用于寻找最短路径或最少操作次数等问题。
在实现BFS时需要使用一个队列来保存待访问的顶点以及一个数组来标记顶点是否已被访问过。这样可以确保每个顶点只被访问一次避免重复访问。
BFS的时间复杂度为O(VE)其中V是顶点数E是边数。在最坏情况下需要遍历图中的所有顶点和边。
查找最短路径
广度优先搜索可回答两类问题。 第一类问题从节点A出发有前往节点B的路径吗在你的人际关系网中有芒果销售商吗 第二类问题从节点A出发前往节点B的哪条路径最短哪个芒果销售商与你的关系最近
广度优先搜索BFS能解决以下问题 最短路径问题BFS可以用来查找图中两个节点之间的最短路径。在无权图中BFS可以找到从一个节点到另一个节点的最短路径因为BFS会按照距离顺序访问节点首次访问到目标节点时就找到了最短路径。 连通性问题BFS可以用来确定图是否是连通的即从一个节点出发是否可以到达图中的所有其他节点。 拓扑排序问题BFS可以用来对有向无环图DAG进行拓扑排序即将图中的所有节点排成线性序列使得对于任意一对有向边 (u, v)节点 u 在序列中都排在节点 v 的前面。 图的遍历BFS可以用来遍历图中的所有节点以便对每个节点进行处理。 迷宫求解BFS可以用来解决迷宫问题即在一个迷宫地图中找到从起点到终点的最短路径。
总之BFS适用于需要按层次逐步扩展搜索范围并且要求在最短时间内找到目标的问题。
队列
队列是一种先进先出First In First OutFIFO的数据结构而栈是一种后进先出Last In First OutLIFO的数据结构。
队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队如果你排在他前面你将先上车。队列的工作原理与此相同。队列类似于栈你不能随机地访问队列中的元素。队列只支持两种操作入队和出队。
小结
广度优先搜索指出是否有从A到B的路径。 如果有广度优先搜索将找出最短路径。 面临类似于寻找最短路径的问题时可尝试使用图来建立模型再使用广度优先搜索来解决问题。 有向图中的边为箭头箭头的方向指定了关系的方向例如rama→adit表示rama欠adit钱。 无向图中的边不带箭头其中的关系是双向的例如ross - rachel表示“ross与rachel约会而rachel也与ross约会”。 队列是先进先出FIFO的。 栈是后进先出LIFO的。 你需要按加入顺序检查搜索列表中的人否则找到的就不是最短路径因此搜索列表必须是队列。 对于检查过的人务必不要再去检查否则可能导致无限循环。
狄克斯特拉算法
什么是狄克斯特拉算法
Dijkstra算法是一种用于计算图中单源最短路径的算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉Edsger W. Dijkstra于1956年发明。它适用于权重非负的有向图或无向图。该算法通过维护一个距离集合来实现在集合中选择一个距离最短的顶点然后更新其他顶点到起始顶点的距离。算法的基本思想是从起始顶点开始逐步扩展离起始顶点距离最短的顶点直到到达目标顶点或者无法继续扩展为止。
Dijkstra算法的步骤如下
初始化将起始顶点的距离设置为0其他顶点的距离设置为无穷大。选择当前距离最短的顶点并标记该顶点已访问。更新与该顶点相邻的顶点的距离如果通过当前顶点到达这些相邻顶点的距离比原来记录的距离短则更新距离值。重复步骤2和步骤3直到所有顶点都被访问或者无法继续更新距离为止。
Dijkstra算法的时间复杂度取决于图的表示方式和数据结构的选择通常为O(V^2)或O(VlogV)其中V是顶点数。
什么时候使用狄克斯特拉算法
狄克斯特拉算法适用于以下情况 单源最短路径问题当需要找到一个图中从单个源点到所有其他顶点的最短路径时可以使用狄克斯特拉算法。 无负权边狄克斯特拉算法要求图中的边权重必须为非负数否则无法保证得到正确的最短路径。 有向图或无向图狄克斯特拉算法适用于有向图或无向图。 稠密图对于稠密图边数接近顶点数的平方狄克斯特拉算法的效率通常优于贝尔曼-福德算法。 网络路由狄克斯特拉算法可以用于计算网络中的最短路径例如互联网路由器在转发数据包时使用狄克斯特拉算法确定最短路径。
总的来说当需要在有向图或无向图中找到单源最短路径并且图中边的权重为非负数时可以考虑使用狄克斯特拉算法。
术语
狄克斯特拉算法用于每条边都有关联数字的图这些数字称为权重weight。 带权重的图称为加权图weighted graph不带权重的图称为非加权图unweighted graph。 要计算非加权图中的最短路径可使用广度优先搜索。要计算加权图中的最短路径可使用狄克斯特拉算法。图还可能有环而环类似右面这样。
这意味着你可从一个节点出发走一圈后又回到这个节点。假设在下面这个带环的图中你要找出从起点到终点的最短路径。
负权边
狄克斯特拉算法Dijkstra算法无法处理带有负权边的图。这是因为狄克斯特拉算法的核心思想是通过逐步找到距离起始顶点最近的顶点来逐步构建最短路径树而负权边可能会导致算法错误地选择非最短路径。
如果图中存在负权边可以考虑使用其他算法如贝尔曼-福德算法Bellman-Ford algorithm。贝尔曼-福德算法可以处理带有负权边的图并能够检测图中是否存在负权环。然而贝尔曼-福德算法的时间复杂度为O(VE)其中V是顶点数E是边数相对于狄克斯特拉算法的O(V^2)或O(VlogV)来说性能可能较差。
贝尔曼-福德算法Bellman-Ford algorithm是一种用于计算图中单源最短路径的算法可以处理带有负权边的图并能够检测图中是否存在负权环。该算法的基本思想是通过对图中所有边进行V-1轮松弛操作V为顶点数逐步逼近所有顶点到源点的最短路径长度。如果经过V-1轮松弛操作后仍然存在可以松弛的边说明图中存在负权环。
贝尔曼-福德算法的步骤如下 初始化将源点到自身的距离设为0其他顶点到源点的距离设为无穷大或一个较大的数值并将所有边的权重记录下来。 进行V-1轮松弛操作对图中的每条边进行松弛操作即尝试通过该边缩短源点到目标顶点的路径长度。 检测负权环如果经过V-1轮松弛操作后仍然存在可以松弛的边则图中存在负权环。
贝尔曼-福德算法的时间复杂度为O(V*E)其中V为顶点数E为边数。算法的空间复杂度为O(V)。虽然贝尔曼-福德算法可以处理带有负权边的图但由于其时间复杂度较高通常在图中存在负权边的情况下使用。
小结
广度优先搜索用于在非加权图中查找最短路径。 狄克斯特拉算法用于在加权图中查找最短路径。 仅当权重为正时狄克斯特拉算法才管用。 如果图中包含负权边请使用贝尔曼-福德算法
贪婪算法
教师调度问题
教室调度问题是一个常见的问题在学校、大学或其他教育机构中经常会遇到。这个问题涉及到如何合理安排教室的使用以满足不同课程和活动的需求同时尽量避免资源的浪费。解决这个问题需要考虑以下几个方面 教室需求: 首先需要了解每个班级或课程对教室的需求包括上课时间、上课时长、上课日期等信息。 教室资源: 然后需要了解教室的资源情况包括教室的数量、大小、设施等信息。 调度策略: 根据教室需求和教室资源情况制定合理的调度策略。这可能涉及到如何合理分配教室、如何安排课程时间表等问题。 调度算法: 最后需要选择合适的调度算法来实现调度策略。常用的调度算法包括贪心算法、动态规划算法、遗传算法等。
通过合理的调度策略和算法可以有效地解决教室调度问题提高教室资源的利用率满足教学需求。
教室调度问题是一个常见的排课问题通常涉及如何合理安排教室的使用以最大化利用资源并满足课程需求。这个问题可以描述为给定一组课程和一组教室每个课程都有特定的时间要求和持续时间每个教室都有容量限制需要确定一个合理的安排使得所有课程都能在规定的时间内顺利进行并且每个教室的容量不被超出。
解决教室调度问题的一种常见方法是使用贪心算法。具体步骤如下 将所有课程按照开始时间进行排序优先安排开始时间早的课程。 初始化一个空的教室列表。 遍历排序后的课程列表对于每个课程 在已有的教室列表中查找是否有合适的教室可用满足课程的时间要求和容量要求。如果找到了合适的教室则将该课程安排在该教室并更新教室的状态。如果没有找到合适的教室则创建一个新的教室并将该课程安排在新教室中。 最终得到的安排即为最优的教室调度方案。
贪心算法的优点是简单高效容易实现并且在某些情况下可以得到较好的近似解。然而贪心算法并不总能保证得到最优解因此在实际应用中可能需要结合其他算法或启发式方法来进一步优化解决方案。
贪婪算法的优点——简单易行贪婪算法很简单每步都采取最优的做法。在这个示例中你每次都选择结束最早的课。用专业术语说就是你每步都选择局部最优解最终得到的就是全局最优解。
背包问题
背包问题是一个经典的组合优化问题通常指在给定容量的背包和一组物品的情况下如何选择物品放入背包使得背包中物品的总价值最大或总重量最大但不能超过背包的容量。
背包问题可以分为两种基本类型0-1背包问题和完全背包问题。 0-1背包问题每种物品只有一件可以选择放入或不放入背包。即每种物品的选择状态是0或1。 完全背包问题每种物品可以选择放入多件即每种物品的选择状态是0到无穷大。
针对这两种背包问题可以使用动态规划算法来求解。
0-1背包问题的动态规划解法
设物品的重量数组为 weights价值数组为 values背包容量为 capacity物品数量为 n。
创建一个二维数组 dp其中 dp[i][j] 表示在前 i 件物品中选择不超过 j 容量的物品的最大价值。则状态转移方程为
dp[i][j] max(dp[i-1][j], dp[i-1][j-weights[i]] values[i]) (if j weights[i])
dp[i][j] dp[i-1][j] (if j weights[i])完全背包问题的动态规划解法
设物品的重量数组为 weights价值数组为 values背包容量为 capacity物品数量为 n。
创建一个一维数组 dp其中 dp[j] 表示在不超过 j 容量的情况下的最大价值。则状态转移方程为
dp[j] max(dp[j], dp[j - weights[i]] values[i]) (if j weights[i])通过填表的方式可以求得背包问题的最优解。这种解法的时间复杂度为 O(n*capacity)。
贪婪策略显然不能获得最优解但非常接近。从这个示例你得到了如下启示在有些情况下完美是优秀的敌人。有时候你只需找到一个能够大致解决问题的算法此时贪婪算法正好可派上用场因为它们实现起来很容易得到的结果又与正确结果相当接近
集合覆盖问题 集合覆盖问题是指给定一些需要覆盖的元素以及一些集合找出最小的集合数使得每个元素至少被一个集合覆盖。
这个问题可以用贪心算法来解决。贪心算法的基本思路是每次选择能覆盖最多未覆盖元素的集合直到所有元素都被覆盖。
具体步骤如下 遍历所有集合找出覆盖了最多未覆盖元素的集合将这个集合加入最终的解集合中。 从未被覆盖的元素中移除被新加入的集合覆盖的元素。 重复上述步骤直到所有元素都被覆盖。
下面是一个示例代码实现了集合覆盖问题的贪心算法解法
def set_cover(sets, elements):# 初始化最终解集合和未覆盖元素集合final_sets []uncovered_elements set(elements)# 循环直到所有元素都被覆盖while uncovered_elements:# 找出覆盖了最多未覆盖元素的集合best_set max(sets, keylambda s: len(s uncovered_elements))final_sets.append(best_set)# 从未覆盖元素中移除被选中集合覆盖的元素uncovered_elements - best_setreturn final_sets# 示例数据
elements set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
sets [set([1, 2, 3, 8, 9]), set([2, 3, 4, 5]), set([3, 5, 6, 7]), set([7, 8, 10])]# 输出结果
print(set_cover(sets, elements))在这个例子中集合 {1, 2, 3, 8, 9} 覆盖了元素 {1, 2, 3, 8, 9}集合 {2, 3, 4, 5} 覆盖了元素 {4, 5}集合 {3, 5, 6, 7} 覆盖了元素 {6, 7}集合 {7, 8, 10} 覆盖了元素 {10}。因此最终的解集合为 [{1, 2, 3, 8, 9}, {2, 3, 4, 5}, {3, 5, 6, 7}, {7, 8, 10}]。
集合覆盖问题是组合优化问题的一种通常描述为在给定一组需要覆盖的元素和一组集合的情况下如何选择最少的集合使得所有的元素都被覆盖到。
形式化地说给定一个全集 U 和一个集合族 S每个集合 S[i] 包含一些元素并且每个元素都属于全集 U。集合覆盖问题要求选择最少的集合 S[i]使得全集 U 中的每个元素都至少属于一个集合 S[i]。
集合覆盖问题是一个 NP-完全问题因此通常采用近似算法来求解。其中贪心算法是一种常用的近似算法它的基本思想是每次选择覆盖了最多未覆盖元素的集合直到所有元素都被覆盖。
贪心算法的具体步骤如下 初始化一个空的集合列表 C用于存放最终选择的集合。 循环遍历直到所有元素都被覆盖 在所有未被覆盖的元素中选择覆盖元素最多的集合 S[i]。将集合 S[i] 加入到集合列表 C 中并更新未被覆盖的元素列表。 返回集合列表 C 作为最终的覆盖方案。
需要注意的是贪心算法并不总能保证得到最优解但在某些情况下可以得到较好的近似解。因此在实际应用中可能需要结合其他算法或启发式方法来进一步优化解决方案。
近似算法
近似算法是一种在合理时间内给出接近最优解的算法。由于许多组合优化问题很难在多项式时间内找到最优解近似算法通过在可接受的时间内找到一个接近最优解的解决方案来解决这些问题。
近似算法的特点包括 快速求解: 近似算法通常能够在较短的时间内给出一个解决方案而不需要花费大量时间来寻找最优解。 接近最优解: 虽然近似算法不能保证得到最优解但它们通常能够得到一个与最优解非常接近的解决方案。 简单易实现: 近似算法通常比精确算法更简单易于理解和实现。 适用范围广: 近似算法可以应用于许多优化问题包括图论、组合优化、排程问题等。
近似算法的常见类型包括贪心算法、局部搜索算法、随机化算法等。这些算法在实际应用中具有重要意义能够为NP难问题提供可行的解决方案。
常见的近似算法包括
贪心算法 贪心算法通过每步选择当前最优解最终得到一个近似最优解。虽然不能保证总是得到最优解但在某些情况下可以得到接近最优解的解决方案。
近似比较算法 这类算法通过将原问题转化为一个较为容易求解的问题并求得其解然后利用得到的解来逼近原问题的解。例如近似比较算法中的常见方法包括对折法、二分法等。
启发式算法 启发式算法通过不断搜索解空间并根据一定的启发信息来引导搜索方向以期望找到一个较好的解。典型的启发式算法包括模拟退火算法、遗传算法等。
虽然近似算法不能保证得到精确的最优解但它们在实际问题中具有重要的应用价值能够在合理的时间内得到较为满意的解决方案。因此近似算法在实际问题求解中得到了广泛的应用。
NP完全问题
NP完全问题是指一类计算问题它们在非确定性多项式时间内可以被解决但尚未找到多项式时间复杂度的解法。NP完全问题具有以下特征
难以解决尚未找到一种有效的算法在多项式时间内解决所有实例。易于验证对于给定的解可以在多项式时间内验证其正确性。具有普适性如果某个问题是NP完全问题那么所有的NP问题都可以在多项式时间内归约为该问题。
NP完全问题的经典例子包括旅行商问题TSP、集合覆盖问题、图的着色问题等。解决NP完全问题的一种方法是通过穷举搜索所有可能的解来寻找最优解但随着问题规模的增大搜索空间呈指数级增长因此在实践中往往不可行。
目前尚未找到快速解决NP完全问题的通用算法但有一些近似算法和启发式算法可以在可接受的时间内给出较好的解。研究NP完全问题对于理解计算复杂性和算法设计具有重要意义。
旅行商问题 旅行商问题TSP是一个经典的组合优化问题目标是在给定一组城市和它们之间的距离找到访问每个城市一次并返回起点城市的最短路径。TSP是一个NP完全问题因为要找到最优解需要遍历所有可能的路径复杂度为O(n!)其中n是城市的数量。
由于TSP的困难性人们通常使用近似算法来寻找可行解。其中一种常用的近似算法是最邻近邻居算法Nearest Neighbor Algorithm。该算法从一个起始城市开始每次选择距离当前城市最近且未访问过的城市作为下一个访问的城市直到所有城市都被访问过然后回到起始城市。这种方法通常会得到一个比较接近最优解的路径但不能保证找到最优解。
另一种常用的近似算法是最小生成树算法如Prim算法或Kruskal算法结合欧拉回路的概念可以用来解决TSP的近似问题。这些算法可以在O(n2logn)或O(n2)的时间复杂度内找到一个相对较好的解。
除了近似算法外还有一些元启发式算法如遗传算法、模拟退火算法和蚁群算法等可以用来解决TSP的近似问题。这些算法通常能够在可接受的时间内找到较好的解但也不能保证找到最优解。
如何识别np完全问题
识别一个问题是否是NP完全问题通常需要经过一系列的步骤和判断 问题的确定性NP完全问题是一类决策问题其答案要么是“是”要么是“否”。问题不能是“是或否”的问题而是需要一个明确的答案。 问题的验证对于给定问题的一个解可以在多项式时间内验证其正确性。也就是说如果一个解是正确的我们可以在多项式时间内验证它。 NP的定义NP问题是可以在多项式时间内验证一个解的问题。这意味着如果我们有一个解我们可以在多项式时间内验证它的正确性。 约化要证明一个问题是NP完全问题通常需要将已知的NP完全问题约化到该问题上。这意味着我们可以使用已知的NP完全问题的解来解决该问题。 证明最后需要证明该问题是NP难的也就是说它至少和NP完全问题一样难。
综上所述要识别一个问题是否是NP完全问题需要证明它是NP问题同时将一个已知的NP完全问题约化到它上面并证明它是NP难的。这是一个相对复杂和困难的过程通常需要一定的数学和计算机科学知识。
小结
贪婪算法寻找局部最优解企图以这种方式获得全局最优解。 对于NP完全问题还没有找到快速解决方案。 面临NP完全问题时最佳的做法是使用近似算法。 贪婪算法易于实现、运行速度快是不错的近似算法
动态规划
背包问题
背包问题是一个经典的组合优化问题在计算机科学和组合数学中被广泛研究。问题可以描述如下
给定一个背包容量为W和一组物品每件物品有一个重量和一个价值。我们需要选择哪些物品放入背包以使得放入背包的物品的总重量不超过背包容量并且总价值最大。
形式化地假设有n件物品每件物品i的重量为wi价值为vi。背包的容量为W。我们定义一个二维数组dp[n1][W1]其中dp[i][j]表示在前i件物品中总重量不超过j的情况下可以获得的最大价值。则背包问题可以用以下递推公式表示
当i0或j0时dp[i][j]0。当jwi时dp[i][j]dp[i-1][j]。当jwi时dp[i][j]max(dp[i-1][j], dp[i-1][j-wi]vi)。
最终问题的解就是dp[n][W]。
背包问题有多种变体包括0-1背包问题每种物品最多放一次、完全背包问题每种物品可以放无限次、多重背包问题每种物品有限制的放置次数等。这些变体可以通过修改递推公式中的条件来描述。
简单算法
背包问题是一个经典的组合优化问题可以用简单算法解决但效率可能不高。其中一个简单的方法是暴力搜索法也称为穷举法或者递归法。具体步骤如下
对于给定的物品和背包容量列出所有可能的物品组合。计算每种组合的总重量和总价值。检查每种组合是否符合背包容量限制如果符合则记录下来。在所有符合条件的组合中找到价值最大的组合。
这种方法的关键是生成所有可能的组合。这种方法的时间复杂度为O(2^n)其中n是物品的数量。对于小规模的问题这种方法可以接受但对于大规模问题这种方法不太实用因为计算时间会随着物品数量的增加而指数级增长。
动态规划
什么是动态规划
动态规划Dynamic Programming简称DP是一种求解最优化问题的方法它将原问题分解为相互重叠的子问题并通过保存子问题的解来避免重复计算从而提高算法效率。动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。
动态规划一般包括以下步骤 定义状态确定问题的状态即问题中需要求解的变量。状态表示问题的不同维度可以是一个或多个变量。 状态转移方程找到问题的状态之间的转移关系即如何从子问题的解推导出原问题的解。状态转移方程描述了问题的最优子结构性质。 初始化初始化边界状态即确定最简单的子问题的解。这些初始状态通常是问题中的一些特殊情况。 计算顺序按照一定顺序计算状态的值通常采用自底向上或自顶向下的方式。 求解最优解根据状态转移方程计算出最终的最优解。
动态规划常用于求解一些具有最优子结构性质的问题如最短路径、最优装载、背包问题等。通过动态规划方法可以有效地解决这些问题并获得最优解。
动态规划是解决背包问题的有效方法它通过将问题分解为子问题并利用子问题的解来求解原始问题。动态规划算法通常包括以下步骤 定义子问题将原始问题分解为子问题。在背包问题中子问题可以定义为对于给定的前i个物品和一个容量为j的背包计算最大的总价值。 确定状态确定动态规划需要保存的状态。在背包问题中状态可以由前i个物品和背包容量j组成。 状态转移方程找到状态之间的关系即如何从子问题的解推导出原始问题的解。在背包问题中状态转移方程可以表示为 dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]) 其中dp[i][j]表示前i个物品放入容量为j的背包的最大价值weight[i]表示第i个物品的重量value[i]表示第i个物品的价值。 初始化初始化边界条件通常表示状态转移数组的第一行和第一列。在背包问题中当没有物品或背包容量为0时最大价值均为0。 计算最终结果根据状态转移方程计算出最终的最优解。在背包问题中最终结果为dp[n][W]其中n为物品的数量W为背包的容量。
动态规划算法的时间复杂度为O(nW)其中n为物品的数量W为背包的容量。动态规划算法在背包问题中的应用可以大大提高计算效率尤其是对于大规模的背包问题。
动态规划问题处理商品一部分可以吗
不能 动态规划通常适用于解决整个商品或问题的情况而不是仅处理商品的一部分。动态规划的核心是将原问题分解为相互重叠的子问题并通过保存子问题的解来避免重复计算从而提高效率。因此如果只处理商品的一部分则可能无法充分利用动态规划的优势。如果商品的一部分也可以独立构成一个完整的子问题并且需要求解的是这部分商品的最优解则可以考虑将问题适当划分并应用动态规划方法。
最长公共子串
最长公共子串问题是指给定两个字符串在两个字符串中找到具有相同字符序列的最长子串。这个子串不需要连续但在两个原始字符串中的相对顺序保持一致。
动态规划是解决最长公共子串问题的常用方法。其基本思想是利用一个二维数组来存储两个字符串中相同位置字符之前的公共子串的长度。具体步骤如下
创建一个二维数组 dp其中 dp[i][j] 表示以字符串1的第 i 个字符和字符串2的第 j 个字符结尾的公共子串的长度。初始化 dp 的第一行和第一列为0表示空字符串与任何字符串的公共子串长度为0。遍历两个字符串的每个字符如果字符相同则 dp[i][j] dp[i-1][j-1] 1表示公共子串的长度加1否则dp[i][j] 0表示当前位置没有公共子串。在遍历过程中记录最长的公共子串的长度和结束位置即 max_length 和 end_index。最终从 end_index 和 max_length 可以回溯出最长公共子串。
下面是一个用动态规划解决最长公共子串问题的示例代码
#include stdio.h
#include string.hvoid longestCommonSubstring(char* str1, char* str2) {int len1 strlen(str1);int len2 strlen(str2);int dp[len1 1][len2 1];int max_length 0;int end_index 0;// Initialize the dp arraymemset(dp, 0, sizeof(dp));for (int i 1; i len1; i) {for (int j 1; j len2; j) {if (str1[i - 1] str2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;if (dp[i][j] max_length) {max_length dp[i][j];end_index i - 1; // or j-1, since they are the same}} else {dp[i][j] 0;}}}// Print the longest common substringif (max_length 0) {printf(No common substring found.\n);} else {printf(Longest common substring is: );for (int i end_index - max_length 1; i end_index; i) {printf(%c, str1[i]);}printf(\n);}
}int main() {char str1[] ABCBA;char str2[] BDCAB;longestCommonSubstring(str1, str2);return 0;
}以上代码将输出最长公共子串 “BC”。
小结
需要在给定约束条件下优化某种指标时动态规划很有用。 问题可分解为离散子问题时可使用动态规划来解决。 每种动态规划解决方案都涉及网格。 单元格中的值通常就是你要优化的值。 每个单元格都是一个子问题因此你需要考虑如何将问题分解为子问题。 没有放之四海皆准的计算动态规划解决方案的公式。
k最近邻算法 k最近邻算法k-Nearest Neighbors, k-NN是一种常用的基于实例的学习算法用于解决分类和回归问题。其基本思想是对于一个未知样本通过查找其在训练集中最相似的k个样本即最近邻来预测该样本的类别或值。
算法步骤如下 确定k的取值选择一个合适的k值通常通过交叉验证等方法确定。 计算距离对于未知样本计算它与训练集中每个样本的距离。常用的距离度量包括欧氏距离、曼哈顿距离等。 找到最近邻选择距离最近的k个样本作为最近邻。 分类或回归对于分类问题使用投票法确定未知样本的类别即选择k个最近邻中出现次数最多的类别作为预测结果对于回归问题使用平均值或加权平均值确定未知样本的值。
k最近邻算法的优点包括简单易懂、无需训练过程、适用于多分类问题等缺点包括计算复杂度高、需要大量存储空间、对异常值敏感等。
什么是回归
回归是一种统计分析方法用于研究变量之间的关系。它通常用于预测一个或多个自变量对因变量的影响。回归分析可以分为简单线性回归和多元线性回归两种情况。 简单线性回归研究一个自变量对一个因变量的影响。其数学表达式为 Y β 0 β 1 X ϵ Y \beta_0 \beta_1X \epsilon Yβ0β1Xϵ 其中 Y Y Y为因变量 X X X为自变量 β 0 \beta_0 β0和 β 1 \beta_1 β1为回归系数 ϵ \epsilon ϵ为误差项。 多元线性回归研究多个自变量对一个因变量的影响。其数学表达式为 Y β 0 β 1 X 1 β 2 X 2 … β p X p ϵ Y \beta_0 \beta_1X_1 \beta_2X_2 \ldots \beta_pX_p \epsilon Yβ0β1X1β2X2…βpXpϵ 其中 Y Y Y为因变量 X 1 , X 2 , … , X p X_1, X_2, \ldots, X_p X1,X2,…,Xp为自变量 β 0 , β 1 , … , β p \beta_0, \beta_1, \ldots, \beta_p β0,β1,…,βp为回归系数 ϵ \epsilon ϵ为误差项。
回归分析的目的是建立一个数学模型描述自变量与因变量之间的关系并用于预测、控制或解释数据。在实际应用中回归分析常用于经济学、社会学、生物学等领域。
机器学习
机器学习是一种人工智能的技术通过让计算机系统从数据中学习模式和规律从而改善其在特定任务上的表现。与传统的编程方式不同机器学习使计算机系统能够从经验中学习而不需要显式地进行编程。
机器学习的基本思想是通过训练模型来学习数据的特征和规律并用于预测、分类、聚类等任务。机器学习可以分为监督学习、无监督学习和强化学习等不同类型具体应用包括自然语言处理、图像识别、推荐系统等领域。
K最近邻KNN算法是一种基本的机器学习算法通常用于分类和回归问题。其基本思想是通过测量不同特征值之间的距离来进行分类或回归预测。具体来说KNN算法包含以下几个步骤 准备数据集收集训练样本数据并且标记好每个样本的类别或结果值。 选择K值确定K的取值K表示选择最近邻的数量。K的选择会影响算法的性能通常通过交叉验证来确定。 计算距离对于测试样本计算它与每个训练样本之间的距离。常用的距离度量包括欧氏距离、曼哈顿距离、闵可夫斯基距离等。 找到最近邻根据计算得到的距离选择距离最近的K个训练样本作为最近邻。 进行预测对于分类问题基于最近邻的类别标签进行投票选择得票最多的类别作为测试样本的预测类别。对于回归问题基于最近邻的结果值进行加权平均或其他计算得到预测结果。
KNN算法的优点包括简单易懂、易于实现、对异常值不敏感等。然而KNN算法的缺点是计算量大、需要大量存储训练数据、对数据分布不均匀敏感等。
OCR技术 OCROptical Character Recognition光学字符识别是一种将图像中的文字转换为可编辑文本的技术。通过OCR技术计算机可以识别并理解印刷体或手写体的文字将其转换为可搜索、可编辑的文本。OCR技术在许多领域都有应用如文档数字化、自动化数据输入、车牌识别、身份证识别等。
垃圾邮件过滤器
垃圾邮件过滤器是一种用于识别和过滤垃圾邮件的软件工具。它通过分析电子邮件的内容、发件人、主题等信息来判断邮件是否是垃圾邮件然后将其移动到垃圾邮件文件夹或者删除。垃圾邮件过滤器通常使用各种技术来识别垃圾邮件包括关键词过滤、黑名单、白名单、机器学习等。这些技术可以帮助用户减少垃圾邮件的干扰提高邮件处理效率。
朴素贝叶斯分类器是一种基于贝叶斯定理的分类算法它假设特征之间相互独立即给定类别的情况下特征之间是条件独立的。这个假设使得朴素贝叶斯分类器的实现变得简单并且在处理大规模数据集时具有很高的效率。
朴素贝叶斯分类器的工作原理如下给定一个待分类的样本计算它属于每个类别的概率然后选择具有最高概率的类别作为样本的分类结果。具体而言对于一个具有n个特征的样本x(x1,x2,…,xn)朴素贝叶斯分类器计算每个类别y的后验概率P(y|x)并选择使得P(y|x)最大的类别作为样本x的分类结果。根据贝叶斯定理后验概率可以表示为P(y|x)P(y)P(x|y)/P(x)其中P(y)是类别y的先验概率P(x|y)是在类别y的条件下观察到样本x的概率P(x)是样本x的先验概率。
朴素贝叶斯分类器在文本分类、垃圾邮件过滤、情感分析等领域都有广泛的应用它的简单性和高效性使得它成为许多机器学习任务的首选算法之一。
朴素贝叶斯分类器的工作原理如下
建立模型根据训练数据集计算每个类别的先验概率以及每个特征在各个类别下的条件概率。特征表示将待分类的文本或数据集表示为特征向量通常使用词袋模型或 TF-IDF 等方法进行特征提取。预测分类对于待分类的文本或数据集计算其属于每个类别的后验概率选择具有最高后验概率的类别作为预测结果。 朴素贝叶斯分类器的优点包括简单、高效、易于实现和解释尤其适用于处理高维度的文本数据。然而它也有一些局限性如对于特征之间的独立性假设要求较高可能会导致在某些情况下性能下降。
next
树
树Tree是一种抽象数据类型它是由nn1个有限节点组成一个具有层次关系的集合。树是一种非线性的数据结构具有以下特点
每个节点有零个或多个子节点。没有父节点的节点称为根节点。每个非根节点有且只有一个父节点。除了根节点外每个子节点可以分为多个不相交的子树。
树的应用非常广泛例如
在计算机科学中树结构被用来实现诸如文件系统、XML解析、编译器语法树等。在数学中树结构被用来描述分支结构例如树形图。在生物学中树结构被用来表示分类关系例如系统发育树。
树的常见操作包括
遍历前序遍历、中序遍历、后序遍历、层序遍历等。插入和删除节点。搜索特定节点。计算树的高度、节点数等。
二叉树
二叉树是一种树形数据结构其中每个节点最多有两个子节点分别称为左子节点和右子节点。二叉树具有以下特性
每个节点最多有两个子节点分别称为左子节点和右子节点。左子节点的值小于或等于父节点的值右子节点的值大于或等于父节点的值这是针对二叉搜索树的性质。对于每个节点其左子树和右子树都是二叉树。
二叉树可以用递归的方式定义一个二叉树要么是空树要么由一个根节点和两个分别为根节点的左子树和右子树的二叉树组成。
二叉树常见的操作包括
遍历前序遍历、中序遍历、后序遍历、层序遍历。插入和删除节点。搜索特定节点。计算树的高度、节点数等。
二叉树的应用非常广泛包括文件系统的组织、数据库的索引结构、编译器中的语法树表示等。
什么是反向索引
反向索引Inverted Index是一种常用于文本检索的数据结构它将文档集合中每个出现的单词映射到包含该单词的文档列表。通常用于搜索引擎中用于快速查找包含特定单词的文档。
例如对于以下文档集合
Document 1: The quick brown fox
Document 2: Jumped over the lazy dog
Document 3: The brown fox is quick生成的反向索引可能如下所示
brown: 1, 3
dog: 2
fox: 1, 3
is: 3
jumped: 2
lazy: 2
over: 2
quick: 1, 3
the: 1, 2, 3在这个例子中每个单词都被映射到包含它的文档编号列表。这样当用户搜索一个单词时可以通过反向索引快速找到包含该单词的文档。
傅里叶变换
傅里叶变换是一种数学变换用于将一个函数通常是一个时域函数转换为另一个函数频域函数它描述了信号在频域的频率和幅度特性。傅里叶变换在信号处理、图像处理、通信等领域有广泛的应用。
傅里叶变换可以分为连续傅里叶变换Continuous Fourier TransformCFT和离散傅里叶变换Discrete Fourier TransformDFT两种形式。
连续傅里叶变换用于连续信号的频域分析将一个连续函数转换为另一个连续函数。离散傅里叶变换用于离散信号的频域分析将一个离散序列转换为另一个离散序列。常见的DFT变体包括快速傅里叶变换Fast Fourier TransformFFT它是一种高效计算DFT的算法。
傅里叶变换的基本思想是任何周期函数都可以由一组正弦函数和余弦函数组合而成。通过傅里叶变换我们可以将一个复杂的信号分解成若干个简单的正弦波或余弦波的叠加从而更好地理解和处理信号。
傅里叶变换是一种数学工具用于将一个函数通常是时域中的函数表示为一组正弦和余弦函数的加权和从而使得函数在频域中的特征更加明显。在信号处理、图像处理、通信等领域有着广泛的应用。
傅里叶变换有两种常见的形式连续傅里叶变换Continuous Fourier TransformCFT和离散傅里叶变换Discrete Fourier TransformDFT。
连续傅里叶变换适用于连续信号将一个连续函数转换为另一个连续函数。公式为 F ( ω ) ∫ − ∞ ∞ f ( t ) e − j ω t d t F(\omega) \int_{-\infty}^{\infty} f(t) e^{-j\omega t} dt F(ω)∫−∞∞f(t)e−jωtdt离散傅里叶变换适用于离散信号将一个离散序列转换为另一个离散序列。公式为 X [ k ] ∑ n 0 N − 1 x [ n ] e − j 2 π N k n X[k] \sum_{n0}^{N-1} x[n] e^{-j\frac{2\pi}{N}kn} X[k]n0∑N−1x[n]e−jN2πkn
在实际应用中离散傅里叶变换特别是快速傅里叶变换FFT更为常见因为它能够高效地计算离散信号的频域表示被广泛应用于信号处理、通信、图像处理等领域。
并行变换
并行算法是指可以同时执行多个计算任务的算法以利用计算资源的并行性从而加速问题的解决。在并行算法中多个计算单元例如处理器、核心、线程等可以同时执行不同的任务或处理同一任务的不同部分以提高算法的效率和性能。
并行算法通常涉及以下几个方面的设计和实现 任务划分将问题分解成多个独立的子任务以便并行执行。任务划分需要考虑任务之间的依赖关系以确保并行执行的正确性和有效性。 通信和同步在并行执行过程中不同的计算单元之间需要进行通信和同步以共享数据、协调任务的执行顺序和结果的合并。通信和同步的设计要尽量减少计算单元之间的等待时间和数据传输延迟以提高算法的并行性能。 负载平衡保持各个计算单元的负载均衡使得每个计算单元的工作量尽量均匀避免出现性能瓶颈和资源浪费。 并行算法的正确性并行算法的设计和实现需要确保算法在并行执行过程中能够产生正确的结果即满足算法的正确性和可靠性要求。
并行算法可以应用于各种领域包括科学计算、数据处理、图像处理、机器学习等。常见的并行算法包括并行排序、并行搜索、并行计算、并行图算法等。并行算法的设计和实现需要考虑到具体应用场景的特点和需求以充分发挥并行计算的优势提高问题解决的效率和速度。
mapreduce
MapReduce是一种用于大规模数据处理的编程模型和计算框架由Google提出。它将大规模的数据集分解成小块然后通过两个主要阶段来处理数据Map阶段和Reduce阶段。
在Map阶段原始数据被拆分成若干独立的小任务每个任务由Map函数处理将输入数据映射为键值对key-value pairs。Map函数的输出作为Reduce函数的输入。
在Reduce阶段所有Map阶段产生的键值对根据键被分组每个键值对组被传递给一个Reduce函数Reduce函数根据键将相同键的所有值进行合并、排序和归约生成最终的输出结果。
MapReduce框架具有易于扩展、容错性强、适用于分布式环境等优点因此被广泛应用于大数据处理领域。Apache Hadoop是一个开源的分布式计算框架实现了MapReduce模型用于处理大规模数据集。
映射函数
映射函数Map function是MapReduce模型中的一个关键组成部分在Map阶段起到重要作用。映射函数接收输入数据的一部分并将其转换为一系列键值对key-value pairs。通常情况下映射函数的输入是原始数据的某个片段输出是由这些片段映射得到的键值对集合。
在映射函数中针对每个输入数据元素都会执行特定的转换逻辑将其映射为一个或多个键值对。这些键值对通常具有两个部分一个键key和一个关联的值value。映射函数的输出键值对集合被用于后续的数据处理阶段。
映射函数的设计取决于具体的数据处理任务和需求通常需要考虑如何有效地将输入数据映射为键值对以便后续的Reduce阶段能够高效地进行处理。在实现映射函数时通常需要考虑数据的解析、转换、过滤等操作以生成符合要求的键值对集合。
归并函数
归并函数Merge function通常在归并排序Merge Sort等算法中使用用于将已经排序好的子数组或子序列合并成一个更大的有序序列。归并函数的主要目的是将两个有序序列合并成一个更大的有序序列。
在归并排序中归并函数是实现分治策略的关键部分。它接收两个有序的子数组或子序列然后将它们合并成一个更大的有序数组或序列。合并过程通常通过比较两个子数组或子序列的元素然后逐个将较小的元素添加到结果数组或序列中来实现。
归并函数的实现方式取决于具体的编程语言和数据结构。通常情况下归并函数会比较两个子数组或子序列的元素并按顺序将它们逐个合并到一个新的数组或序列中。在合并过程中归并函数可能需要使用额外的空间来存储临时数据以便正确地合并两个有序序列。
布隆过滤器和HyperLogLog
布隆过滤器Bloom Filter是一种数据结构用于快速判断一个元素是否可能在一个集合中。它通过使用多个哈希函数和一个位数组来实现。当一个元素被加入到布隆过滤器中时通过多个哈希函数将元素映射到位数组中的多个位置并将这些位置的值设为1。当需要判断一个元素是否在集合中时同样通过多个哈希函数将元素映射到位数组的位置并检查这些位置的值是否都为1。如果所有位置的值都为1则说明元素可能在集合中如果有一个位置的值不为1则元素肯定不在集合中。布隆过滤器的特点是可以高效地判断一个元素是否在集合中但有一定的误判率。
HyperLogLog是一种基数估计算法用于估计一个集合中不重复元素的个数。它通过使用一个位数组和一些哈希函数来实现。当一个元素被加入到HyperLogLog中时首先通过哈希函数将元素映射到一个值然后根据这个值的二进制表示找到位数组中的位置并将该位置的值更新为元素的哈希值中的前导0的个数加1。当需要估计集合中不重复元素的个数时统计位数组中值为0的位置的个数并根据这个值来估计不重复元素的个数。HyperLogLog的特点是能够高效地估计大规模数据集合的基数并且在空间和时间上的开销比较小。
sha算法
SHASecure Hash Algorithm是一组密码散列函数标准用于计算数据的散列值。SHA算法通常用于数据完整性校验、数字签名、消息认证码MAC等安全应用中。SHA算法的输出通常为一个固定长度的散列值不同版本的SHA算法支持不同的输出长度如SHA-1160位、SHA-256256位、SHA-512512位等。这些算法在设计上都考虑了对抗性、安全性和效率等方面的需求。
SHA算法的基本过程包括以下步骤
初始化设置初始的散列值常量。数据填充将输入数据进行填充使得填充后的数据长度满足算法的要求。分组处理将填充后的数据按照固定长度的分组进行处理。迭代计算对每个分组进行迭代计算生成中间散列值。最终计算对所有中间散列值进行最终的计算生成最终的散列值。
SHA算法具有以下特点
不可逆性由散列值无法推导出原始数据。固定输出长度不同版本的SHA算法有不同的输出长度但是对于同一版本的算法输出长度是固定的。抗碰撞性对于不同的输入生成的散列值应该是唯一的避免碰撞。
SHA算法在网络安全、数据完整性验证、数字签名等领域有着广泛的应用。
比较函数和sha函数
比较文件的SHA算法通常是指计算文件内容的SHA哈希值以便于验证文件的完整性和唯一性。常见的SHA算法有SHA-1、SHA-256、SHA-512等。这些算法在计算上有所不同主要体现在以下几个方面 输出长度不同版本的SHA算法有不同的输出长度SHA-1输出160位SHA-256输出256位SHA-512输出512位。 安全性随着计算能力的增强对于SHA-1算法的攻击已经变得可行。因此一般建议选择更安全的SHA-256或SHA-512算法。 计算速度通常来说输出长度更长的算法需要更多的计算时间。因此SHA-1的计算速度可能比SHA-256和SHA-512要快一些。 应用场景根据安全性和计算性能的要求选择适合的SHA算法。对于一般的文件完整性校验SHA-256已经足够安全和快速。
在实际应用中可以根据具体的安全需求和计算性能选择适合的SHA算法来比较文件的哈希值。
检查密码和sha算法
要检查密码是否正确通常会使用哈希函数对输入的密码进行哈希运算然后与存储的哈希值进行比较。常见的方法是使用SHA算法如SHA-256对密码进行哈希处理然后将哈希值与存储的哈希值进行比较。
具体步骤如下
用户输入密码。使用SHA-256或其他哈希算法对用户输入的密码进行哈希运算得到哈希值。将得到的哈希值与存储的正确哈希值进行比较。如果两个哈希值相同则密码正确否则密码错误。
在实际应用中为了增加安全性通常还会对密码进行加盐salt处理即在密码哈希之前将一个随机生成的字符串与密码合并然后再进行哈希运算。这样可以避免彩虹表攻击等安全问题。
局部敏感的散列函数
局部敏感哈希Locality Sensitive HashingLSH是一种将相似的数据映射到相同的桶中以便在高维空间中快速找到相似数据的技术。LSH的主要思想是通过哈希函数将相似的数据映射到相同的桶中从而使得在查询时可以只考虑相似的数据所在的桶而不必遍历整个数据集。
LSH主要应用于大规模数据集中的近似最近邻搜索Approximate Nearest Neighbor Search问题例如在推荐系统中寻找相似用户或商品、在搜索引擎中寻找相似文档等。LSH算法通常包括两个主要步骤哈希函数的选择和桶的划分。常用的LSH算法包括MinHash、SimHash等。
LSH算法的优点是能够在保持一定的查询精度的同时显著减少计算量适用于处理大规模数据集的近似查询问题。
Diffie-Hellman密钥交换
Diffie-Hellman密钥交换是一种安全协议用于在不安全的通信信道上交换密钥以便安全地加密通信数据。该协议的核心思想是双方通过一些数学运算离散对数运算计算出一个共享的密钥而不需要直接传输密钥本身。
具体步骤如下
双方事先协商好两个公开的参数素数p和一个生成元gg是p的一个原根。双方各自选择一个私密的随机数私钥记为a和b。双方根据公式计算出公开的部分公钥 Alice计算 A g^a mod pBob计算 B g^b mod p 双方交换公钥然后再根据对方的公钥和自己的私钥计算出共享的密钥 Alice计算 K B^a mod pBob计算 K A^b mod p 最终双方得到的密钥K相同可以用于加密通信数据。
Diffie-Hellman密钥交换的关键在于离散对数问题的困难性即给定p、g和g^a mod p计算出a的值是非常困难的因此即使公开的p、g和g^a mod p也无法轻易地推算出a的值保证了密钥交换的安全性。
线性规划
线性规划Linear Programming简称LP是运筹学中的一个重要分支主要研究在线性约束条件下线性目标函数的极值问题。它是一种数学理论和方法用于辅助人们进行科学管理并为合理利用有限资源制定最佳决策提供科学依据。
线性规划问题通常由两部分组成目标函数和约束条件。目标函数是决策变量所要达到的目标通常表示为线性函数约束条件则是决策变量需要满足的限制条件也表示为线性等式或不等式。通过求解线性规划问题可以找到在满足所有约束条件的前提下使目标函数达到最优最大或最小的决策变量值。
线性规划在多个领域有广泛应用包括军事作战、经济分析、经营管理和工程技术等。例如在微观经济学和商业管理领域线性规划被用于解决收入最大化或生产过程的成本最小化等问题。
随着计算机技术的发展和普及线性规划的应用越来越广泛。通过使用专门的线性规划软件或算法可以高效地求解复杂的线性规划问题为实际问题的决策提供有力支持。
