GC算法的O序

Question

垃圾收集算法是多项式还是指数？
如果是多项式 - 它们会与堆大小成线性关系还是二次关系？
初步了解，Parallel 和 CMS GC 会与需要访问的对象数量成线性关系。

但是如果您对此有任何意见，我们将不胜感激。

Answer 1

理想机器的时间复杂度。实际上 CPU 的缓存大小相对有限，GC 可以非常随机且高效地访问内存。

GC 算法是 O(n)，但您的数据大小与 CPU 缓存甚至您的数据排列的随机性都很重要。例如如果有很多从老一代到新一代的引用，你的 GC 必须做更多的工作。