数据结构和算法
数据结构
- 数组(Array):一种线性数据结构,可以存储相同类型的元素,支持基于索引的快速访问。
- 链表(Linked List):由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。
- 栈(Stack):遵循后进先出(LIFO)原则的线性数据结构,只能在一端(栈顶)进行添加或删除操作。
- 队列(Queue):遵循先进先出(FIFO)原则的线性数据结构,两端分别进行添加(队尾)和删除(队首)操作。
- 哈希表(Hash Table):通过哈希函数将键映射到表中的位置来访问数据,支持高效的查找、插入和删除操作。
- 树(Tree):由节点组成的层次结构,每个节点有零个或多个子节点,常用于表示具有层次关系的数据。
- 二叉树(Binary Tree):每个节点最多有两个子节点的树结构,常用于实现各种高效的算法。
- 二叉搜索树(Binary Search Tree, BST):二叉树的变体,左子树上的所有节点的值小于或等于节点的值,右子树上的所有节点的值大于节点的值。
- 堆(Heap):一种特殊的树结构,通常用于实现优先队列,根节点是最大的(最大堆)或最小的(最小堆)。
- 图(Graph):由顶点(节点)和边组成,用于表示实体间的关系。
排序算法
- 冒泡排序(Bubble Sort):通过重复遍历待排序的数列,比较每对相邻元素的大小,并在必要时交换它们的位置。每一轮遍历都会将最大的元素“冒泡”到它应该在的位置。
- 选择排序(Selection Sort):它不断地从待排序的元素中选择最小的元素,并将其放到已排序序列的末尾。
- 插入排序(Insertion Sort):通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 O(1) 的额外空间的排序)。
- 快速排序(Quick Sort):通过选取一个“基准”元素,将数组分为两个子数组,一个包含小于基准的元素,另一个包含大于基准的元素。然后递归地在两个子数组上重复这个过程。
- 归并排序(Merge Sort)
- 堆排序(Heap Sort)
搜索算法
- 线性搜索(Linear Search):从数据结构的开始或结束逐个检查每个元素,直到找到所需的元素或搜索完所有元素。
- 二分搜索(Binary Search):在有序数组中,通过比较数组中间的元素与目标值来确定搜索区间。如果目标值等于中间元素,则搜索成功;如果目标值小于中间元素,则在左半部分继续搜索;如果目标值大于中间元素,则在右半部分继续搜索。这个过程将重复进行,每次搜索范围减半,直到找到目标值或搜索范围为空。
机器学习算法
- 线性回归(Linear Regression):
- 用于预测连续值输出,例如房价预测。
- 通过拟合数据点并找到最佳拟合直线(或曲线)来建模变量之间的关系。
- 逻辑回归(Logistic Regression):
- 虽然名字中有“回归”,但它用于分类问题,特别是二分类问题。
- 通过使用逻辑函数(如Sigmoid函数)将线性回归的输出映射到0和1之间,用于表示概率。
- 决策树(Decision Tree):
- 用于分类和回归问题。
- 通过学习简单的决策规则从数据特征中推断出目标值。
- 随机森林(Random Forest):
- 是决策树的集成学习方法,用于分类和回归问题。
- 构建多个决策树并将它们的预测结果结合起来,以提高模型的准确性和稳定性。
- 支持向量机(SVM, Support Vector Machine):
- 用于分类和回归问题,特别擅长于二分类问题。
- 通过找到数据点之间的最优边界线(或超平面),这条边界线最大化了不同类别之间的边界。
- 朴素贝叶斯(Naive Bayes):
- 基于贝叶斯定理的分类算法,特别适用于大量特征的数据集,如文本分类。
- 假设特征之间相互独立,通过计算每个类别的后验概率来预测新样本的类别。
- K最近邻(K-Nearest Neighbors, KNN):
- 一种简单的算法,用于分类和回归问题。
- 通过查找测试数据点的K个最近邻居来进行预测。
- K均值聚类(K-Means Clustering):
- 一种无监督学习算法,用于将数据点分组成K个簇。
- 通过最小化簇内数据点与簇中心的距离来进行聚类。