标记-清除算法时间复杂度为o(n+m)，其中n为堆中对象总数、m为可达存活对象数；标记阶段仅遍历可达对象，清除阶段必须扫描整个堆，且全程stw导致实际延迟显著。
标记-清除算法的时间复杂度是 O(n + m)，其中 n 是堆中对象总数，m 是从 GC Roots 可达的存活对象数量。它不是均摊开销，而是单次停顿内集中消耗，实际延迟常比理论值更明显。
标记阶段：耗时取决于存活对象数 m
该阶段从 GC Roots（如栈帧引用、静态变量、JNI 引用）出发，遍历所有可达对象并打标。只访问“能走到”的对象，不扫描全堆。因此：
- 若存活对象少（如新生代 Minor GC，98% 对象死亡），标记极快；
- 若存在长链表、深层嵌套容器或大量跨代引用，访问模式易引发缓存失效，CPU 和内存延迟上升；
- 标记本身不依赖写屏障，但若搭配 CMS 等并发收集器，初始标记/重新标记会额外引入屏障开销。
清除阶段：耗时取决于总对象数 n
必须线性扫描整个堆内存区域，逐个检查标记位，回收未标记对象，并将其加入空闲链表。这一过程无法跳过：
- 即使堆中 99% 是垃圾，仍需遍历全部 n 个位置；
- 堆大小不变时，清除时间基本稳定，与存活率无关；
- 空闲链表随碎片增多而变长，后续分配时查找合适块的成本上升（最坏 O(k)，k 为空闲块数）。
Stop-the-World 放大实际开销
整个标记+清除过程必须暂停应用线程，用户感知为一次明显卡顿。此时：
- 缓存频繁失效：标记阶段随机跳转、清除阶段稀疏布局，导致大量 cache miss；
- 无并发能力：纯标记-清除不支持并发执行，现代 JVM 通常仅将其作为老年代回收的基础环节，再叠加整理（Compact）或配合分代策略缓解影响；
- 碎片不增加当次耗时，但会间接推高后续 GC 频率，形成时间开销正反馈。
分代设计如何优化整体复杂度
JVM 不靠单个算法取胜，而是按对象生命周期分治：
- 年轻代用复制算法：只遍历存活对象（m 很小），时间复杂度 O(m)，且无碎片、分配快；
- 老年代用标记-清除+整理：先 O(n+m) 标记清除，再 O(m) 整理压缩，避免碎片恶化；
- 弱分代假说支撑了这种分工——98% 对象在 Eden 区即死亡，让复制算法高效成立；强分代假说则保障老年代对象稳定，使标记-整理比纯复制更经济。
