system.nanotime() 只能测量实际耗时，不能确定时间复杂度；它适用于相同环境下相似实现的相对性能比较，但必须配合理论分析，通过多规模输入、固定环境和关注增长比值来辅助验证复杂度趋势。
System.nanoTime() 不能评估算法的时间复杂度。它只能测量某次运行在特定环境下的真实耗时，而时间复杂度（如 O(n)、O(n²)）是描述算法随输入规模增长的渐进理论行为，与硬件、JVM、缓存、GC 等无关。
换句话说：
- 你用
nanoTime测出“数组长度从 1000 增到 2000，耗时从 5000 纳秒变成 19800 纳秒”，这只是一个实验数据点； - 但仅凭这个，无法得出它是 O(n²)，因为可能是 JIT 预热不均、缓存未命中突增、或偶然触发了一次 Young GC——这些都会让耗时非线性跳变。
nanoTime 的正确定位：测「耗时」，不测「复杂度」
- ✅ 它适合：比较两个相似实现（如
ArrayList.get()vsLinkedList.get()）在相同 JVM、相同数据规模下的相对快慢； - ❌ 它不适合：代替数学推导或大 O 分析。哪怕你画了 n～耗时散点图、拟合出一条抛物线，那也只是经验观察，不是时间复杂度证明。
如果你想用 nanoTime 辅助理解复杂度趋势，必须做对三件事
-
固定环境，只变输入规模
- 每次测试都新建独立 JVM（或至少彻底预热+清空旧对象）；
- 输入数据每次都重新生成（避免复用引用导致缓存/逃逸分析干扰）；
- 使用不同规模的输入（如 n = 1000, 2000, 4000, 8000），每组跑足够轮次取中位数。
-
测的是「增长关系」，不是「绝对数值」
- 关注耗时比值：若 n 翻倍，耗时约翻 4 倍 → 倾向于 O(n²)；约翻 2 倍 → 倾向于 O(n)；基本不变 → 倾向于 O(1)；
- 但需排除常数项和低阶项干扰（比如 O(n + 100000) 在小 n 下看起来像 O(1)）。
-
必须配合理论分析，不能反推
- 先看代码结构：几层循环？递归深度？分治还是遍历？这是判断复杂度的第一步；
- 再用 nanoTime 验证：比如你推导出某排序是 O(n log n)，那么实测 n=1e5 和 n=1e6 时，耗时比应接近 log(1e6)/log(1e5) ≈ 1.15 倍（乘上常数后合理放大）；
- 若实测严重偏离（如翻了 10 倍），说明可能有隐含高开销操作（如字符串拼接、同步块、未关闭的流），这时 nanoTime 帮你定位瓶颈，而非否定复杂度。
为什么单靠 nanoTime 得不出可靠结论？
- JIT 编译会动态优化：前 1000 次慢，第 10000 次可能被内联，耗时骤降；
- GC 干扰：一次 Minor GC 可暂停几十毫秒，远超算法本身纳秒级开销；
- 硬件因素：CPU 频率升降、TLB 缺失、分支预测失败，都会让同段代码每次耗时浮动 20% 以上；
- 单次调用噪声大：
nanoTime()自身调用成本约 40–100 纳秒，测一个 50 纳秒的操作，结果基本不可信。
更务实的做法：用 nanoTime 找“哪里慢”，而不是“是什么复杂度”
- 把算法拆成子步骤（如：读输入 → 预处理 → 主循环 → 输出格式化）；
- 对每个子步骤单独套 nanoTime（注意预热、防优化、批量执行）；
- 查看哪一段耗时占比最高、是否随 n 显著增长；
- 这样你能快速发现：哦，不是主循环慢，是 JSON 解析占了 90% 时间——那优化方向就明确了。
不复杂但容易忽略。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
