搜索算法的分类与特性搜索算法是用于在数据集中查找特定元素的算法。以下是几种常见的搜索算法及其起源、原理、时间复杂度和空间复杂度的概述：
线性搜索（Linear Search）代码语言：txt复制- 起源：线性搜索是一种最基础的搜索算法，其起源可以追溯到计算机科学的早期。
- 原理：
线性搜索逐一比较数据集中的每个元素，直到找到目标元素或遍历完整个数据集。
- 时间复杂度：
在最坏情况下，需要遍历整个数据集，因此时间复杂度为O(n)，其中n是数据集中的元素数量。
- 空间复杂度：
线性搜索的空间复杂度很低，因为算法只需要几个额外的变量来跟踪当前查找的位置，所以通常为O(1)。 本算法详解见此文：常用的搜索算法之线性搜索（Linear Search）
二分搜索（Binary Search）代码语言：txt复制- 起源：二分搜索算法是由John Mauchly在1946年发明的，适用于有序数组。
- 原理：
二分搜索从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；否则，根据目标值与中间值的大小关系，在数组的左半部分或右半部分继续搜索，如此反复进行。
- 时间复杂度：
二分搜索每次都将搜索范围减半，因此时间复杂度为O(log n)，其中n是数组的长度。
- 空间复杂度：
二分搜索的空间复杂度为O(1)，因为它只需要常数级别的额外空间来存储变量（如数组的开始和结束索引，以及要查找的目标值）。本算法详解见此文：常用的搜索算法之二分搜索（Binary Search）
哈希搜索（Hashing Search）代码语言：txt复制- 起源：哈希搜索的思想起源于哈希函数和哈希表的概念，这些概念在计算机科学中有广泛的应用。
- 原理：
哈希搜索根据关键字计算其在哈希表中的位置，然后直接访问该位置上的元素。如果该位置上的元素不是要查找的元素，则顺序向后查找。
- 时间复杂度：
哈希查找的时间复杂度是O(1)，即常数时间，因为哈希表中的每个元素都有一个唯一的位置。然而，如果发生哈希冲突（即不同的关键字计算得到相同的哈希值），则可能需要遍历哈希表中的链表，导致时间复杂度增加。
- 空间复杂度：
哈希搜索的空间复杂度取决于哈希表的大小和哈希冲突的处理方式。在理想情况下，哈希表的大小与数据集中的元素数量相当，因此空间复杂度为O(n)。然而，为了处理哈希冲突，可能需要额外的空间来存储链表或其他数据结构，这会增加空间复杂度。本算法详解见此文：常用的搜索算法之哈希搜索（Hashing Search）
深度优先搜索（DFS）代码语言：txt复制- 起源：深度优先搜索是图论中的经典算法之一，其起源可以追溯到计算机科学的早期。
- 原理：
DFS从图的某个起始顶点开始，沿着一条路径尽可能深入地访问图中的所有顶点，直到不能继续为止，然后返回并探索其他路径。具体实现时，通常使用栈数据结构来辅助搜索。
- 时间复杂度：
DFS的时间复杂度取决于图的结构和搜索策略。在最坏情况下（即当图为完全图时），需要访问所有的顶点和边，因此时间复杂度为O(V+E)，其中V是顶点数，E是边数。
- 空间复杂度：
DFS的空间复杂度也取决于图的结构和搜索策略。在最坏情况下（即当图为链状结构时），需要存储的元素数量达到O(V)级别，因此空间复杂度也是O(V)。然而，在实际应用中，由于递归调用和栈的使用，空间复杂度可能会受到一定的限制。本算法详解见此文：常用的搜索算法之深度优先搜索
广度优先搜索（BFS）代码语言：txt复制- 起源：广度优先搜索是另一种图论中的经典算法，与DFS类似，其起源也可以追溯到计算机科学的早期。
- 原理：
BFS从图的某个起始顶点开始，先依次访问这个顶点的所有邻居顶点，然后再按照距离逐层遍历图中的所有顶点。具体实现时，通常使用队列数据结构来辅助搜索。
- 时间复杂度和空间复杂度：
与DFS类似，BFS的时间复杂度和空间复杂度也取决于图的结构和搜索策略。在最坏情况下（即当图为完全二叉树时），需要访问所有的顶点和边，因此时间复杂度和空间复杂度均为O(V+E)。然而，在实际应用中，由于队列的使用和可能的剪枝策略，空间复杂度可能会有所不同。本算法详解见此文：层次遍历-Level Order Traversal