大 O 复杂度速查
时间 / 空间复杂度 · 常见算法对照 · 点击复制
第一节
关于本工具
About手写归并排序时，常常写到一半忘了递归边界该不该加一；查 LeetCode 题解，又得从代码里反推复杂度。输入算法名称或伪代码片段，这个工具直接给出时间与空间复杂度，并附上递归树或主定理的推导简图。所有计算在浏览器本地完成，公式不离开当前页面——笔试前速查、代码审查时快速校验复杂度都用得上。
使用场景
面试手撕算法
字节跳动后端二面，面试官让手写一个 LRU 缓存。候选人知道用哈希表+双向链表，但不确定 get 和 put 操作的时间复杂度是否严格 O(1)。刷题时用本工具速查链表、哈希表各操作的大 O，确认双向链表删除节点 O(1)、哈希查找 O(1) 平均，组合后整体符合要求。面试当场画出复杂度表格，面试官点头通过。
重构老系统接口
维护一个日活 50 万的电商后台，订单列表接口每次返回全量数据，用户翻到第 10 页后响应超时。开发怀疑是后端 SQL 没加分页，但前端也用了数组 slice。用本工具查：数组 slice 是 O(n)，每次翻页都复制前 10 页数据，总复杂度 O(n²)。改成游标分页后，每页 O(1)，接口从 3 秒降到 80 毫秒。
LeetCode 周赛压轴题
周赛第四题，数据范围 10^5，暴力 O(n²) 必超时。选手想到用优先队列优化，但不确定堆的 push/pop 复杂度。打开本工具查：二叉堆插入 O(log n)、删除 O(log n)，整体 O(n log n) 可过。赛后看题解，官方确实用堆，复杂度一致。本工具避免了「感觉能过但不敢写」的犹豫。
校招笔试限时优化
美团笔试题：给一个 10^6 长度的数组，求每个元素右侧第一个比它大的数。用单调栈 O(n) 能过，但考生只想到双重循环 O(n²)，算下来 10^12 次操作，笔试平台 1 秒必超。用本工具速查栈操作复杂度：入栈出栈各 O(1)，整体 O(n)。改完后 0.3 秒出结果，通过全部测试用例。
数据库索引设计评审
团队设计订单表，业务方要求按用户 ID + 下单时间查询。DBA 建议建联合索引 (user_id, create_time)，但有人质疑索引 B+ 树查找复杂度。用本工具查：B+ 树等值查找 O(log n)，范围查找 O(log n + k)，联合索引最左匹配后性能达标。评审会当场拿出复杂度图说服全组，避免了建错索引导致慢查询。
第二节
使用指南
Getting Started使用步骤
- 1在「算法」下拉框中选择目标算法（如二分查找、冒泡排序），右侧立即显示对应的时间/空间复杂度图表
- 2点击复杂度符号（如 O(log n)）旁的「详情」图标，展开该复杂度的典型场景与数据规模参考
- 3在「数据规模」滑块上拖动调整输入量（如 1000 条），图表中对应复杂度曲线自动高亮并标注近似操作次数
- 4点击图表右上角「导出」按钮，将当前视图保存为 PNG 图片，方便嵌入文档或笔记
输入输出示例
| 输入 | 输出 | 说明 |
|---|---|---|
| 冒泡排序（Bubble Sort） | 时间复杂度：最坏 O(n²) / 平均 O(n²) / 最好 O(n)；空间复杂度：O(1) | 常规：最基础的排序算法，展示最好/最坏/平均三种时间复杂度的区分，以及原地排序（O(1) 空间）的典型特征 |
| 二分查找（Binary Search） | 时间复杂度：O(log n)；空间复杂度：O(1) | 常规：对数复杂度代表，验证工具对递归/迭代两种实现是否都能正确输出 O(log n)，而不是误判为 O(n) |
| 斐波那契数列（递归实现） | 时间复杂度：O(2ⁿ)；空间复杂度：O(n) | 边界：递归实现的指数级复杂度，空间复杂度来自调用栈深度，区别于迭代实现的 O(n) 时间 / O(1) 空间 |
| 哈希表查找（Hash Table Lookup） | 时间复杂度：平均 O(1) / 最坏 O(n)；空间复杂度：O(n) | 边界：展示平均 vs 最坏情况的差异，最坏 O(n) 由哈希冲突导致，用户常忽略最坏情况 |
| 动态规划：0/1 背包问题（DP 表解法） | 时间复杂度：O(nW)；空间复杂度：O(nW) | 易错：nW 不是多项式复杂度（W 是输入数值而非位数），用户常误以为这是多项式时间算法，工具需要明确标注为伪多项式 |
| 图的深度优先搜索（DFS，邻接表） | 时间复杂度：O(V + E)；空间复杂度：O(V) | 易错：用户常混淆邻接矩阵（O(V²)）与邻接表（O(V+E)）的区别，此示例验证工具是否区分存储结构 |
| 快速排序（Quick Sort，最坏情况） | 时间复杂度：最坏 O(n²) / 平均 O(n log n) / 最好 O(n log n)；空间复杂度：O(log n) | 边界：展示最坏情况（已排序数组 + 固定选首元素）导致退化为 O(n²)，空间复杂度来自递归栈（原地分区实现） |
常见错误对照
1.混淆大 O 与最坏情况
✗ 错误
认为 O(n²) 是算法在所有输入下的运行时间✓ 修复
O(n²) 描述的是最坏情况下的上界增长趋势大 O 表示最坏情况的上界，不代表平均或最好情况。例如快速排序最坏 O(n²)，但平均 O(n log n)。
2.忽略常数因子，误判实际性能
✗ 错误
认为 O(2n) 比 O(n) 慢，所以选 O(n) 算法✓ 修复
O(2n) 和 O(n) 都是 O(n)，实际差异看常数和输入规模大 O 忽略常数因子和低阶项。O(1000n) 仍是 O(n)，但常数很大时在小规模输入下可能比 O(n²) 慢。
3.把 O(log n) 的底数当作重要参数
✗ 错误
认为 O(log₂ n) 比 O(log₁₀ n) 快✓ 修复
所有对数复杂度 O(log n) 底数不同只差常数倍，忽略换底公式 log_a n = log_b n / log_b a，底数差异被大 O 的常数因子吸收，不改变复杂度等级。
4.嵌套循环一定 O(n²) 的误判
✗ 错误
看到两层 for 循环就写 O(n²)✓ 修复
内层循环次数不依赖外层变量时才是 O(n²)，否则需具体分析例如外层 i 从 0 到 n，内层 j 从 i 到 n，总次数为 n(n+1)/2，实际 O(n²) 但常数不同。若内层固定 10 次，则 O(n)。
5.忽略递归调用栈的空间复杂度
✗ 错误
计算斐波那契递归时只考虑 O(1) 额外空间✓ 修复
递归深度 n 导致调用栈占用 O(n) 空间递归函数每次调用压栈，空间复杂度包括栈深度。斐波那契递归深度 n，空间 O(n)；迭代法才 O(1)。
6.把 O(1) 空间误解为不占内存
✗ 错误
认为 O(1) 空间算法完全不使用额外内存✓ 修复
O(1) 表示额外空间是常数，不随输入规模增长O(1) 可以包含几个固定变量（如指针、计数器），但若输入本身存储不算在内。例如原地反转链表是 O(1) 额外空间。
7.误以为 O(n log n) 总是比 O(n²) 好
✗ 错误
任何场景都选 O(n log n) 算法✓ 修复
当 n 很小时（如 n<10），O(n²) 的简单实现可能更快大 O 描述增长趋势，不反映常数和实际运行时间。小规模输入下，O(n²) 的简单插入排序可能比 O(n log n) 的归并排序快。
8.混淆时间复杂度和空间复杂度
✗ 错误
用时间复杂度的分析方式推导空间复杂度✓ 修复
空间复杂度只关注额外分配的内存，不包含输入本身时间看操作次数，空间看内存分配。例如哈希表插入 O(1) 时间，但存储 n 个元素需要 O(n) 空间。
第三节
工作原理
How It Works核心公式
T(n) = O(f(n))，其中 f(n) 为输入规模 n 下增长最快的项
变量说明
T(n)算法执行时间或空间占用n输入数据规模，如数组长度f(n)主导增长率的函数，如 n²
示例
冒泡排序对 10 个元素排序：最坏情况比较次数 = n(n-1)/2 = 10×9/2 = 45，主导项为 n²，故 T(n) = O(n²)。
用户输入
本地处理
输出结果
第五节
常见问题
Q & A问这个工具能查红黑树的时间复杂度吗？＋
答
可以。本工具覆盖常见数据结构与算法的时间/空间复杂度，包括红黑树、AVL树、B树、哈希表、堆等。查找时直接输入「红黑树」或「Red-Black Tree」即可看到搜索、插入、删除的均摊和最坏情况复杂度。如果没命中，检查拼写或尝试英文名。
问为什么同一个算法，这里写 O(n log n)，有的地方写 O(n²)？＋
答
复杂度取决于具体实现和输入条件。例如快速排序，平均是 O(n log n)，但最坏情况（已排序数组且选第一个元素为pivot）退化为 O(n²)。本工具同时标注平均、最坏和最好三列，选择「最坏」列就能看到最差情况。如果只看一列，默认显示平均复杂度。
问空间复杂度里的 O(1) 和 O(n) 到底差多少？＋
答
O(1) 表示额外内存不随输入规模增长，比如原地交换排序；O(n) 表示需要和输入等量的额外空间，比如归并排序的辅助数组。举例：对 100 万个数排序，O(1) 可能只多几 KB 临时变量，O(n) 会多占 8 MB（假设 64 位整数）。本工具在空间复杂度列直接给出符号，点击符号会弹出典型内存占用的数值估算。
问这个图能导出或保存吗？＋
答
当前版本支持截图保存。图区域右上角有「截图」按钮，点击后自动下载 PNG 格式的复杂度对照图。如果需要在文档里引用，建议截图后裁剪标题栏。不支持直接导出 SVG 或 CSV，后续版本可能会加导出表格功能。
问为什么我搜「二分查找」出来 O(log n)，但我写的代码跑起来很慢？＋
答
O(log n) 是理论比较次数，实际慢可能因为：1) 数据不是有序数组（链表无法随机访问），二分查找退化为 O(n)；2) 数据量太小，log n 的优势不明显；3) 递归实现有函数调用开销。本工具假设最理想的数据结构和实现，实际工程中还要考虑缓存、分支预测等因素。可以对比同一数据量的线性查找实测时间。
问这个工具是离线用的吗？会不会上传我的代码？＋
答
完全离线。本工具是纯前端实现（FE），所有计算和图表渲染都在浏览器本地完成，不向服务器发送任何数据。即使断网也能正常使用。页面加载后关闭网络，刷新仍可用，因为资源已缓存。隐私方面可以放心，不会记录搜索历史或输入内容。
问哈希表查复杂度说是 O(1)，但冲突多的时候是不是骗人的？＋
答
不骗人，但需要加前提。理想情况下（均匀哈希、负载因子低）是 O(1) 均摊；冲突严重时（比如所有 key 哈希到同一桶）退化为 O(n)。本工具在哈希表条目下标注了「均摊 O(1)，最坏 O(n)」，并给出建议负载因子（通常 ≤ 0.75）。如果实际使用中遇到大量冲突，考虑换用更均匀的哈希函数或扩容。
问这个工具能对比两个算法的复杂度吗？＋
答
可以。在搜索框输入两个算法名，结果区会并排显示它们的复杂度对比图，用不同颜色区分。也可以在「对比模式」下分别添加算法到对比列表，最多同时对比 4 个。对比时自动高亮差异项（比如一个 O(n) 另一个 O(log n) 会标红），方便快速判断优劣。
隐私保证所有计算与处理均在你的浏览器本地完成，输入数据不会上传服务器，也不会保存或共享。