标记-清除算法时间复杂度为o(n+m)，其中n为堆中对象总数、m为gc roots可达的存活对象数；标记阶段耗时正比于m，清除阶段耗时正比于n，且全程需stop-the-world。
标记-清除算法的时间复杂度是 O(n + m)，其中 n 是堆中所有对象的总数，m 是从 GC Roots 可达的存活对象数量。它在时间开销上呈现明显的两阶段特征：标记阶段耗时与存活对象数 m 成正比，清除阶段耗时则与总对象数 n 成正比。
标记阶段：遍历可达图，时间取决于存活对象
该阶段从 GC Roots（如栈帧引用、静态变量、JNI 引用等）出发，采用深度或广度优先方式遍历所有可达对象，并为每个存活对象打上标记（例如设置对象头中的 mark bit）。实际开销主要由图的规模决定——不是所有对象都要访问，而是只访问“能走到”的那些。因此若存活对象少（如新生代），标记很快；若老年代大量对象长期存活，标记过程会明显变长。
- 典型场景：一次 Minor GC 中，Eden 区对象死亡率常超 98%，标记仅需处理极少数幸存者，非常轻量
- 风险点：若存在深链引用（如长链表、嵌套容器）或大量跨代引用，标记可能触发缓存不友好访问，加剧 CPU 时间与内存延迟开销
清除阶段：线性扫描全堆，时间取决于总对象数
清除阶段必须遍历整个堆内存区域（无论对象是否存活），检查每个对象的标记位。未被标记的对象即被判定为垃圾，其内存被归入空闲链表（free list）管理。这一步无法跳过，因此即使堆中 99% 是垃圾，仍需扫描全部 n 个对象位置。
- 代价固定：只要堆大小不变，清除时间基本稳定，与存活率无关
- 隐性开销：维护空闲链表需插入/合并操作，碎片多时链表变长，后续分配时查找合适块的平均成本上升（最坏 O(k)，k 为空闲块数量）
整体时间开销受哪些因素放大？
实际运行中，理论复杂度常被以下现实因素拉高：
- Stop-the-World 延迟集中：整个标记+清除过程必须暂停应用线程，用户感知的是单次长停顿，而非均摊开销
- 缓存失效严重：标记阶段随机跳转访问对象，清除阶段顺序扫描但对象布局稀疏，易引发多次 cache miss
- 写屏障无直接参与：纯标记-清除本身不依赖写屏障，但现代 JVM 若搭配分代或并发收集器（如 CMS 的初始标记/重新标记），会额外引入屏障开销
- 碎片整理缺失：虽不增加 GC 当次耗时，但碎片累积导致后续分配失败频发，间接引发更频繁的 GC，形成时间开销正反馈
