算法（结合算法图解）

算法简介
- 简单查找
- 二分查找法
选择排序
- 内存的工作原理
- 数组和链表
- 数组
- 选择排序
- 小结
递归
- - 小梗要想学会递归，首先要学会递归。
- 递归的基线条件和递归条件
- 递归和栈
- 小结
快速排序
- 分而治之
- 快速排序
- 合并排序
- 时间复杂度的平均情况和最糟情况
- 小结
散列表
- 散列函数
- 缓冲
- 小结
- 性能
- 装填因子
- 良好的哈希函数特性
- 小结
广度优先搜索
- 图
- 广度优先遍历
- 查找最短路径
- 队列
- 小结
狄克斯特拉算法
- 什么是狄克斯特拉算法
- 什么时候使用狄克斯特拉算法
- 术语
- 负权边
- 小结
贪婪算法
- 教师调度问题
- 背包问题
- 集合覆盖问题
- 近似算法
- NP完全问题
- 如何识别np完全问题
- 小结
动态规划
- 背包问题
- 简单算法
- 动态规划
- 动态规划问题处理商品一部分可以吗？
- 最长公共子串
- 小结
k最近邻算法
- 什么是回归
- 机器学习
- 垃圾邮件过滤器
next
- 树
- - 二叉树
- 什么是反向索引
- 傅里叶变换
- 并行变换
- mapreduce
- 映射函数
- 归并函数
- 布隆过滤器和HyperLogLog
- sha算法
- 比较函数和sha函数
- 检查密码和sha算法
- 局部敏感的散列函数
- Diffie-Hellman密钥交换
- 线性规划

在这里插入图片描述

算法简介

算法是一组完成任务的指令。算法与编程语言无关算法是一种思考。

简单查找

简单查找（Simple Search），也称为线性查找（Linear Search），是一种基本的查找算法，适用于未排序或部分排序的数组。其基本思想是逐个地对数组元素进行比较，直到找到目标元素或遍历完整个数组为止。

简单查找的实现非常直观，通常用于简单的问题或者对性能要求不高的场景。然而，它的时间复杂度为 O(n)，其中 n 是数组的长度，即在最坏情况下需要遍历整个数组才能确定目标元素的位置，效率较低。

二分查找法

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是通过不断将待查找区间分成两半，并利用目标值与中间元素的比较结果来确定下一步查找的区间，直到找到目标值或者区间缩小到空为止。

二分查找适用于满足以下条件的场景：

有序数组： 数组必须是有序的（升序或降序），否则无法利用二分查找的特性。
静态数据结构： 二分查找适用于静态的数据结构，即查找操作频率远远大于插入、删除操作的场景。因为每次插入、删除操作都需要对数组进行调整，破坏了数组的有序性。
连续存储空间： 二分查找通常使用数组这种连续存储空间实现，不适用于链式存储结构。
单调性： 如果数组中存在重复元素，只能找到其中一个元素的位置。另外，二分查找通常是找到第一个满足条件的元素，如果要找最后一个元素，则需要稍作修改。

时间复杂度为 O(log n)，效率较高。

在这里插入图片描述
你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。

假设你从1开始依次往上猜，猜测过程会是这样。

在这里插入图片描述
但这种方式是连续的询问，方法比较笨。

可以一次排除一半，增加效率
在这里插入图片描述

在这里插入图片描述

大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都
将余下的数字排除一半。接下来，你猜63（50和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 Conquer，D&C）是一种解决问题的思想和算法范式，它将一个大问题分解成多个相似的小问题，然后递归地解决这些小问题，并将它们的解合并起来，得到原问题的解。分治法通常包括三个步骤：

分解（Divide）：将原问题分解成若干个规模较小的子问题，这些子问题是原问题的规模的一个子集。
解决（Conquer）：递归地解决这些子问题。如果子问题的规模足够小，并且可以直接求解，则不再递归，直接求解。
合并（Combine）：将子问题的解合并成原问题的解。

分治法常用于解决具有以下特点的问题：

原问题可以分解成规模较小的相似子问题。
子问题可以独立求解，且子问题的解可以合并成原问题的解。
使用分治法求解的问题，递归求解的复杂度通常可以表示为递归深度乘以每层的复杂度。

分治法的经典应用包括归并排序、快速排序和二分查找等。

快速排序

快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C

**快速排序（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)。

为了避免快速排序的最坏情况，通常可以采用随机化的方法来选择基准元素，或者使用三数取中法等策略来选择基准元素，这样可以尽可能地降低出现最坏情况的概率，从而提高快速排序的性能。

小结

 D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(logn)的速度比O(n)快得多。

散列表

二分查找的速度非常快。但某些时刻还是需要更快的方式
在这里插入图片描述

散列函数

散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。
在这里插入图片描述
如果用专业术语来表达的话，我们会说，散列函数“将输入映射到数字”。你可能认为散列函数输出的数字没什么规律，但其实散列函数必须满足一些要求。
 它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。
 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

散列函数准确地指出了价格的存储位置，你根本不用查找！之所以能够这样，具体原因如下。
 散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个数字。因此，你可首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来确定鳄梨的价格存储在什么地方。
 散列函数将不同的输入映射到不同的索引。avocado映射到索引4，milk映射到索引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(V+E)，其中V是顶点数，E是边数。在最坏情况下，需要遍历图中的所有顶点和边。

查找最短路径

广度优先搜索可回答两类问题。
 第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销售商吗？）
 第二类问题：从节点A出发，前往节点B的哪条路径最短？（哪个芒果销售商与你的关系最近？

广度优先搜索（BFS）能解决以下问题：

最短路径问题：BFS可以用来查找图中两个节点之间的最短路径。在无权图中，BFS可以找到从一个节点到另一个节点的最短路径，因为BFS会按照距离顺序访问节点，首次访问到目标节点时，就找到了最短路径。
连通性问题：BFS可以用来确定图是否是连通的，即从一个节点出发是否可以到达图中的所有其他节点。
拓扑排序问题：BFS可以用来对有向无环图（DAG）进行拓扑排序，即将图中的所有节点排成线性序列，使得对于任意一对有向边 (u, v)，节点 u 在序列中都排在节点 v 的前面。
图的遍历：BFS可以用来遍历图中的所有节点，以便对每个节点进行处理。
迷宫求解：BFS可以用来解决迷宫问题，即在一个迷宫地图中找到从起点到终点的最短路径。

总之，BFS适用于需要按层次逐步扩展搜索范围，并且要求在最短时间内找到目标的问题。

队列

队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。

队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车。队列的工作原理与此相同。队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。
在这里插入图片描述

小结

 广度优先搜索指出是否有从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, key=lambda s: len(s & uncovered_elements))
        final_sets.append(best_set)

        # 从未覆盖元素中移除被选中集合覆盖的元素
        uncovered_elements -= best_set

    return 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(n^2logn)或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[n+1][W+1]，其中dp[i][j]表示在前i件物品中，总重量不超过j的情况下，可以获得的最大价值。则背包问题可以用以下递推公式表示：

当i=0或j=0时，dp[i][j]=0。
当j<wi时，dp[i][j]=dp[i-1][j]。
当j>=wi时，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.h>

void 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 array
    memset(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 substring
    if (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最近邻算法的优点包括简单易懂、无需训练过程、适用于多分类问题等；缺点包括计算复杂度高、需要大量存储空间、对异常值敏感等。

什么是回归

回归是一种统计分析方法，用于研究变量之间的关系。它通常用于预测一个或多个自变量对因变量的影响。回归分析可以分为简单线性回归和多元线性回归两种情况。

简单线性回归：研究一个自变量对一个因变量的影响。其数学表达式为：
$\beta_0 + \beta_1X + \epsilon$
其中， $Y$ 为因变量， $X$ 为自变量， $\beta_0$ 和 $\beta_1$ 为回归系数， $\epsilon$ 为误差项。
多元线性回归：研究多个自变量对一个因变量的影响。其数学表达式为：
$\beta_0 + \beta_1X_1 + \beta_2X_2 + \ldots + \beta_pX_p + \epsilon$
其中， $Y$ 为因变量， $X_1, X_2, \ldots, X_p$ 为自变量， $\beta_0, \beta_1, \ldots, \beta_p$ 为回归系数， $\epsilon$ 为误差项。

回归分析的目的是建立一个数学模型，描述自变量与因变量之间的关系，并用于预测、控制或解释数据。在实际应用中，回归分析常用于经济学、社会学、生物学等领域。

机器学习

机器学习是一种人工智能的技术，通过让计算机系统从数据中学习模式和规律，从而改善其在特定任务上的表现。与传统的编程方式不同，机器学习使计算机系统能够从经验中学习，而不需要显式地进行编程。

机器学习的基本思想是通过训练模型来学习数据的特征和规律，并用于预测、分类、聚类等任务。机器学习可以分为监督学习、无监督学习和强化学习等不同类型，具体应用包括自然语言处理、图像识别、推荐系统等领域。

K最近邻（KNN）算法是一种基本的机器学习算法，通常用于分类和回归问题。其基本思想是通过测量不同特征值之间的距离来进行分类或回归预测。具体来说，KNN算法包含以下几个步骤：

准备数据集：收集训练样本数据，并且标记好每个样本的类别或结果值。
选择K值：确定K的取值，K表示选择最近邻的数量。K的选择会影响算法的性能，通常通过交叉验证来确定。
计算距离：对于测试样本，计算它与每个训练样本之间的距离。常用的距离度量包括欧氏距离、曼哈顿距离、闵可夫斯基距离等。
找到最近邻：根据计算得到的距离，选择距离最近的K个训练样本作为最近邻。
进行预测：对于分类问题，基于最近邻的类别标签进行投票，选择得票最多的类别作为测试样本的预测类别。对于回归问题，基于最近邻的结果值进行加权平均或其他计算得到预测结果。

KNN算法的优点包括简单易懂、易于实现、对异常值不敏感等。然而，KNN算法的缺点是计算量大、需要大量存储训练数据、对数据分布不均匀敏感等。

OCR技术
OCR（Optical Character Recognition，光学字符识别）是一种将图像中的文字转换为可编辑文本的技术。通过OCR技术，计算机可以识别并理解印刷体或手写体的文字，将其转换为可搜索、可编辑的文本。OCR技术在许多领域都有应用，如文档数字化、自动化数据输入、车牌识别、身份证识别等。

垃圾邮件过滤器

垃圾邮件过滤器是一种用于识别和过滤垃圾邮件的软件工具。它通过分析电子邮件的内容、发件人、主题等信息来判断邮件是否是垃圾邮件，然后将其移动到垃圾邮件文件夹或者删除。垃圾邮件过滤器通常使用各种技术来识别垃圾邮件，包括关键词过滤、黑名单、白名单、机器学习等。这些技术可以帮助用户减少垃圾邮件的干扰，提高邮件处理效率。

朴素贝叶斯分类器是一种基于贝叶斯定理的分类算法，它假设特征之间相互独立，即给定类别的情况下，特征之间是条件独立的。这个假设使得朴素贝叶斯分类器的实现变得简单，并且在处理大规模数据集时具有很高的效率。

朴素贝叶斯分类器在文本分类、垃圾邮件过滤、情感分析等领域都有广泛的应用，它的简单性和高效性使得它成为许多机器学习任务的首选算法之一。

朴素贝叶斯分类器的工作原理如下：

建立模型：根据训练数据集，计算每个类别的先验概率以及每个特征在各个类别下的条件概率。
特征表示：将待分类的文本或数据集表示为特征向量，通常使用词袋模型或 TF-IDF 等方法进行特征提取。
预测分类：对于待分类的文本或数据集，计算其属于每个类别的后验概率，选择具有最高后验概率的类别作为预测结果。
朴素贝叶斯分类器的优点包括简单、高效、易于实现和解释，尤其适用于处理高维度的文本数据。然而，它也有一些局限性，如对于特征之间的独立性假设要求较高，可能会导致在某些情况下性能下降。

树

树（Tree）是一种抽象数据类型，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。树是一种非线性的数据结构，具有以下特点：

每个节点有零个或多个子节点。
没有父节点的节点称为根节点。
每个非根节点有且只有一个父节点。
除了根节点外，每个子节点可以分为多个不相交的子树。

树的应用非常广泛，例如：

在计算机科学中，树结构被用来实现诸如文件系统、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 Transform，CFT）和离散傅里叶变换（Discrete Fourier Transform，DFT）两种形式。

连续傅里叶变换：用于连续信号的频域分析，将一个连续函数转换为另一个连续函数。
离散傅里叶变换：用于离散信号的频域分析，将一个离散序列转换为另一个离散序列。常见的DFT变体包括快速傅里叶变换（Fast Fourier Transform，FFT），它是一种高效计算DFT的算法。

傅里叶变换的基本思想是任何周期函数都可以由一组正弦函数和余弦函数组合而成。通过傅里叶变换，我们可以将一个复杂的信号分解成若干个简单的正弦波或余弦波的叠加，从而更好地理解和处理信号。

傅里叶变换是一种数学工具，用于将一个函数（通常是时域中的函数）表示为一组正弦和余弦函数的加权和，从而使得函数在频域中的特征更加明显。在信号处理、图像处理、通信等领域有着广泛的应用。

傅里叶变换有两种常见的形式：连续傅里叶变换（Continuous Fourier Transform，CFT）和离散傅里叶变换（Discrete Fourier Transform，DFT）。

连续傅里叶变换：适用于连续信号，将一个连续函数转换为另一个连续函数。公式为：
$F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-j\omega t} dt$
离散傅里叶变换：适用于离散信号，将一个离散序列转换为另一个离散序列。公式为：
$\sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}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算法

SHA（Secure Hash Algorithm）是一组密码散列函数标准，用于计算数据的散列值。SHA算法通常用于数据完整性校验、数字签名、消息认证码（MAC）等安全应用中。SHA算法的输出通常为一个固定长度的散列值，不同版本的SHA算法支持不同的输出长度，如SHA-1（160位）、SHA-256（256位）、SHA-512（512位）等。这些算法在设计上都考虑了对抗性、安全性和效率等方面的需求。

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 Hashing，LSH）是一种将相似的数据映射到相同的桶中，以便在高维空间中快速找到相似数据的技术。LSH的主要思想是通过哈希函数将相似的数据映射到相同的桶中，从而使得在查询时可以只考虑相似的数据所在的桶，而不必遍历整个数据集。

LSH主要应用于大规模数据集中的近似最近邻搜索（Approximate Nearest Neighbor Search）问题，例如在推荐系统中寻找相似用户或商品、在搜索引擎中寻找相似文档等。LSH算法通常包括两个主要步骤：哈希函数的选择和桶的划分。常用的LSH算法包括MinHash、SimHash等。

LSH算法的优点是能够在保持一定的查询精度的同时，显著减少计算量，适用于处理大规模数据集的近似查询问题。