java 常见算法

一、通用基础

时间／空间复杂度分析
- 熟练掌握 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 等常见复杂度，并能针对业务场景做权衡。
常见数据结构
- 数组、链表、栈、队列、哈希表（HashMap）、堆（优先队列）、树（尤其是二分搜索树、B-树/B+ 树）、图。
排序与查找
- 快速排序、归并排序、堆排序、二分查找，以及在特定场景下的稳定排序（如归并、插入排序）。

时间／空间复杂度分析

O(1) - 常数时间

含义：执行时间不随数据量的变化而变化。每次操作都是固定的时间。

业务推荐：
- 数组和哈希表查找：例如在缓存中查找用户信息、通过ID访问数据库记录。
- 栈和队列的操作：例如任务调度系统的入队和出队操作。
- 获取当前时间或状态：例如获取当前的系统时间、获取某个全局状态。
适用场景：
- 数据结构操作：如果你需要在常数时间内完成查找、插入或删除，选择哈希表或数组。
- 简单数据访问：访问数组中的特定位置，或哈希表中某个键值对。

O(log n) - 对数时间

含义：执行时间随着数据量的增加呈对数级别增长，通常出现在分治算法中。

业务推荐：
- 二分查找：例如在电商平台中快速查找商品（数据有序时）。
- 平衡二叉树操作：如AVL树、红黑树等，适用于数据库索引、内存中的有序数据结构。
- 堆：如优先队列，适用于任务调度系统，处理具有优先级的任务。
适用场景：
- 快速查找：当数据已经排序时，使用二分查找。
- 动态数据存储：当需要频繁查找、插入、删除有序数据时，使用平衡二叉树。
- 调度系统：任务优先级处理时使用堆。

O(n) - 线性时间**

含义：执行时间随着数据量的增大成线性关系。

业务推荐：
- 遍历数据：例如遍历订单列表或用户列表，进行一些统计、修改等操作。
- 线性查找：如在无序数组中查找某个元素。
- 数据统计：如计算总销量、统计订单数量等。
适用场景：
- 数据遍历和处理：如果你需要访问每一个元素并进行处理，选择 O(n) 的算法（如遍历数组、链表等）。
- 无序数据查找：例如在用户列表中查找指定用户。

O(n log n) - 线性对数时间

含义：执行时间随着数据量的增加成对数级别增长，通常适用于高效排序或分治算法。

业务推荐：
- 高效排序：如快速排序、归并排序，用于大规模数据的排序（如商品排序、订单排序等）。
- 合并操作：例如将两个有序的数据源合并成一个有序数据。
- 图算法：某些图算法（如 Dijkstra 算法）用 O(n log n) 复杂度处理最短路径问题。
适用场景：
- 大规模排序：当数据量较大时，需要高效的排序算法（如快速排序、归并排序）。
- 合并两个数据集：当需要将两个有序数组或链表合并时，采用合并排序等方法。

O(n²) - 二次时间

含义：执行时间随着数据量的增加呈二次增长，通常出现在嵌套循环中。

业务推荐：
- 暴力排序：如冒泡排序、插入排序、选择排序，这些算法适用于数据量较小的场景。
- 矩阵运算：如矩阵乘法的传统算法，或二维数组遍历。
- 图的邻接矩阵表示：对于图的操作，如果使用邻接矩阵存储图的边，某些操作（如遍历节点）会导致 O(n²) 时间复杂度。
适用场景：
- 小规模数据排序：当数据量较小（比如少于1000个数据），使用 O(n²) 的暴力算法是可行的。
- 二维数据结构操作：处理二维数组、矩阵时会涉及 O(n²) 时间复杂度。
推荐：对于大数据量，建议避免 O(n²) 算法，尤其是排序操作，可以考虑 O(n log n) 的高效算法。

O(n³) - 三次时间

含义：执行时间随着数据量的增大呈三次增长，通常出现于处理三维数据的场景。

业务推荐：
- 三维矩阵计算：如三维数组的操作或图形处理中的某些算法。
- 复杂的图算法：一些特定的图算法，如果图的规模较小，可能采用三次时间复杂度。
适用场景：
- 矩阵运算：如果需要进行三维矩阵运算，或者涉及到多个嵌套循环的复杂运算时，时间复杂度为 O(n³)。
- 全局优化问题：比如在一些复杂的全局优化问题中，暴力求解可能涉及三重循环，时间复杂度为 O(n³)。
推荐：尽量避免使用 O(n³) 的算法，尤其是当数据量较大时，考虑是否有优化的解法。

O(2^n) - 指数时间

含义：执行时间随着数据规模的增加呈指数增长，通常出现在递归算法中，尤其是穷举型的算法。

业务推荐：
- 递归解法：例如斐波那契数列的递归解法、旅行商问题的暴力解法。
- 暴力破解：在解某些组合优化问题时，穷举所有可能解的情况，时间复杂度为 O(2^n)。
适用场景：
- 小规模问题的递归解法：对于数据量较小的组合优化问题，如求解旅行商问题时，递归穷举可能可行。
- 小规模的递归分支问题：如树形结构的递归遍历等。
推荐：对于大规模数据，避免使用 O(2^n) 算法。需要优化时，可以考虑使用动态规划、贪心算法等更高效的算法。

O(n!) - 阶乘时间

含义：执行时间随着数据量的增加呈阶乘增长，通常用于处理排列问题。

业务推荐：
- 全排列问题：如生成所有可能的任务调度顺序、排列组合。
- 解空间树的遍历：某些复杂的组合问题，暴力求解需要遍历所有可能的解空间，导致阶乘时间复杂度。
适用场景：
- 排列组合问题：如果你需要列举数据的所有排列、组合，可能会用到 O(n!) 算法。
- 小规模优化问题：例如小规模的任务调度优化问题，需要暴力搜索最优解。
推荐：对于大规模问题，避免使用 O(n!) 算法。可以使用启发式算法或动态规划来优化解法。

总结

O(1)：适用于需要快速查找或修改单一元素的场景，如缓存、栈和队列。
O(log n)：适用于查找、插入和删除有序数据，推荐使用二分查找、平衡树等。
O(n)：适用于遍历数据、进行数据统计等场景，选择线性时间算法。
O(n log n)：适用于高效排序、大规模数据处理，推荐使用快速排序、归并排序。
O(n²)：适用于小规模数据的暴力算法、二维数据结构处理，避免大数据量时使用。
O(n³)：适用于三维数据处理、复杂图算法，但避免大规模数据时使用。
O(2^n)：适用于小规模递归解法或暴力破解问题，大规模数据时需要优化。
O(n!)：适用于全排列问题、小规模的组合问题，大数据量时不可行。

通过结合业务场景和算法特点，你可以根据需求快速找到合适的算法，在项目中做出合理的选择。

二、前端需关注的算法

DOM 树/虚拟 DOM 差分算法
- React、Vue 等前端框架的核心，通过递归或键值映射实现最小化的 DOM 更新。
节流（Throttle）与防抖（Debounce）
- 优化高频操作（resize、scroll、input 等）的触发频率，降低渲染压力。
动画与缓动函数（Easing）
- 常见缓动公式（linear、ease-in/out、cubic-bezier 等），以及基于 requestAnimationFrame 的帧率控制。
路径查找（可选，用于游戏/可视化）
- A*、Dijkstra 算法，用于前端可视化或游戏中的路径规划。
前端缓存策略
- LRU（最近最少使用）、LFU（最不常用）缓存淘汰策略，在 Service Worker 或内存缓存中应用。
加密／哈希
- MD5、SHA 系列（用于数据完整性校验）、Base64（简单编码），以及对称／非对称加密（Web Crypto API）。

三、后端需掌握的算法

负载均衡算法
- 轮询（Round Robin）、加权轮询、最少连接、IP Hash，以及一致性哈希（Consistent Hashing，用于分布式缓存如 Redis Cluster）。
缓存淘汰策略
- LRU、LFU、TTL（时效失效）等，在 Redis、Memcached、CDN 缓存设计中非常重要。
数据库索引与查询优化
- B+ 树、哈希索引；查询执行计划分析；事务隔离与并发控制（两段锁、MVCC）。
分布式一致性 & 共识算法
- Paxos、Raft，用于分布式存储系统（Etcd、ZooKeeper）。
消息队列与调度算法
- 优先级队列、延迟队列、轮询调度、工作窃取（Work Stealing）；常见在 Kafka、RabbitMQ、Celery 中应用。
限流与降级
- 漏桶（Leaky Bucket）、令牌桶（Token Bucket），以及基于滑动窗口的计数算法。
加密与安全
- 对称加密（AES）、非对称加密（RSA）、数字签名、TLS 握手流程中的密钥交换算法（DH、ECDH）等。

四、爬虫（Spider/Crawler）专用算法

爬取策略
- 广度优先（BFS）、深度优先（DFS）、优先队列（针对聚焦爬虫，选择性爬取）。
URL 去重与发现
- 哈希（Hash）、布隆过滤器（Bloom Filter）用于海量 URL 的快速去重。
抓取调度与并发控制
- 基于异步（async/await）、多线程/多进程的任务队列；限速与重试策略。
HTML 解析与数据抽取
- XPath、CSS Selector、正则表达式，必要时结合 NLP 分词／实体识别（如 jieba、spaCy）。
抗封锁与隐匿策略
- 动态代理池管理、IP 轮换；随机 UA 生成；登录／模拟行为（可选 Selenium 或 Puppeteer）。
内容相似性检测
- 文本 shingling、余弦相似度、MinHash，用于去重或判定改动增量爬取。