常见算法
排序算法
冒泡排序（Bubble Sort）
原理：通过重复比较相邻元素并交换它们的位置，逐步将最大（或最小）元素“冒泡”到数组的一端。
时间复杂度：O(n²)
应用：简单数据集的排序，但效率较低。
选择排序（Selection Sort）
原理：每一轮选择未排序部分的最小（或最大）元素，放置到已排序部分的末尾。
时间复杂度：O(n²)
应用：简单实现，适用于小数据集。
插入排序（Insertion Sort）
原理：将数组分为已排序和未排序两部分，逐步将未排序元素插入已排序部分的正确位置。
时间复杂度：O(n²)，但在部分已排序的情况下效率较高。
应用：适合小数据集和近乎排序的数据。
快速排序（Quick Sort）
原理：通过选择一个“基准”元素，将数组分为两部分，左侧小于基准，右侧大于基准，然后递归排序两部分。
时间复杂度：O(n log n)（平均情况），O(n²)（最坏情况）。
应用：广泛用于各种排序任务，尤其是大数据集。
归并排序（Merge Sort）
原理：将数组分成两半，递归地对两部分进行排序，然后合并已排序的部分。
时间复杂度：O(n log n)
应用：适用于需要稳定排序和大数据集的情况。
堆排序（Heap Sort）
原理：利用堆数据结构构建最大堆（或最小堆），每次取出堆顶元素放到已排序部分。
时间复杂度：O(n log n)
应用：适用于需要高效排序的场景。
线性查找（Linear Search）
原理：逐个检查数组元素，直到找到目标元素或遍历完整个数组。
时间复杂度：O(n)
应用：适用于未排序的数组。
二分查找（Binary Search）
原理：在已排序数组中，反复将查找范围减半，直到找到目标元素或查找范围为空。
时间复杂度：O(log n)
应用：效率高，适用于大量数据的查找。
哈希查找（Hash Table）
原理：利用哈希函数将键映射到存储位置，支持快速的插入和查找操作。
时间复杂度：O(1)（平均情况）
应用：常用于需要快速查找的场景，如缓存和索引。
图算法
深度优先搜索（DFS, Depth-First Search）
原理：从某个起始节点开始，尽可能深地遍历图的分支，直到无法继续，然后回溯。
应用：用于寻找路径、拓扑排序和连通性检查等。
广度优先搜索（BFS, Breadth-First Search）
原理：从起始节点出发，逐层遍历图的所有邻接节点，直到找到目标节点。
应用：最短路径搜索和层次遍历等。
Dijkstra算法（最短路径）
原理：用于计算从源节点到所有其他节点的最短路径，使用贪心策略逐步更新路径长度。
时间复杂度：O((V + E) log V)（V为节点数，E为边数）
应用：网络路由和地图导航。
Floyd-Warshall算法
原理：动态规划方法，计算所有节点对之间的最短路径。
时间复杂度：O(V³)
应用：适用于小型图的全源最短路径计算。
Kruskal算法（最小生成树）
原理：构建最小生成树，通过不断选择权重最小的边，避免形成环。
时间复杂度：O(E log E)
应用：用于网络设计和最小成本连通问题。
Prim算法（最小生成树）
原理：从任意节点开始，逐步将最小边加入生成树，直到连接所有节点。
时间复杂度：O(E log V)
应用：适用于稠密图的最小生成树构建。
动态规划
斐波那契数列（Fibonacci Sequence）
原理：用递推关系定义数列，使用缓存避免重复计算。
时间复杂度：O(n)
应用：数学和计算问题的基础。
背包问题（0/1 Knapsack Problem）
原理：通过选择物品使总重量不超过限制，最大化总价值。
时间复杂度：O(nW)（n为物品数量，W为背包容量）
应用：资源分配和财务管理。
最长公共子序列（Longest Common Subsequence）
原理：通过动态规划寻找两个序列的最长公共子序列。
时间复杂度：O(mn)（m和n为两个序列的长度）
应用：文本比较和生物信息学。
最长递增子序列（Longest Increasing Subsequence）
原理：通过动态规划找出序列中最长的递增子序列。
时间复杂度：O(n²)（可优化至O(n log n)）
应用：数据分析和趋势识别。
贪心算法
活动选择问题（Activity Selection Problem）
原理：选择不重叠的活动，使得活动数量最大。
时间复杂度：O(n log n)（排序后）
应用：调度和资源分配。
最小硬币问题（Coin Change Problem）
原理：选择最少数量的硬币凑成特定金额，通常假设硬币面额为正。
时间复杂度：O(n)（在特定情况下）
应用：金融系统和支付解决方案。
霍夫曼编码（Huffman Coding）
原理：构建前缀编码，使得字符的编码长度与其出现频率成反比。
时间复杂度：O(n log n)
应用：数据压缩和编码。
字符串算法
KMP算法（字符串匹配）
原理：通过预处理模式串，避免重复比较，提高匹配效率。
时间复杂度：O(n + m)（n为文本长度，m为模式长度）
应用：字符串搜索和文本处理。
Rabin-Karp算法（字符串匹配）
原理：使用哈希函数快速比较字符串的子串，解决多模式匹配问题。
时间复杂度：O(n + m)（平均情况）
应用：查找重复文本和模式匹配。
Trie树（前缀树）
原理：一种树形数据结构，存储动态集合或关联数组，主要用于字符串查找。
时间复杂度：O(m)（m为查询字符串的长度）
应用：自动补全、拼写检查和前缀匹配。
数学算法
欧几里得算法（求最大公约数）
原理：通过递归求解两个数的最大公约数。
时间复杂度：O(log(min(a, b)))
应用：计算公约数和简化分数。
快速幂算法（Exponentiation by Squaring）
原理：利用分治法快速计算大整数的幂。
时间复杂度：O(log n)
应用：大数计算和加密算法。
素数筛选算法（埃拉托斯特尼筛法）
原理：通过迭代标记合数，找出小于某一数的所有素数。
时间复杂度：O(n log log n)
应用：数论和密码学。
