垃圾收集运行时间成本的大O分析

当以垃圾收集语言推理运行时成本时，根据'n'（列表中元素的数量），语句的成本是多少？如myList = null;？为了论证的缘故，请将列表视为单引用链接列表，无需最终确定。垃圾收集运行时间成本的大O分析

更一般地说，我正在寻找任何有关如何使用GC语言分析运行时成本的信息。

2010-09-20 pauldoo

我自己的想法是，成本可能是O（1）或O（n）取决于收集器的实施。在标记和扫描收集器中，无法访问的对象根本无法到达，所以我可以想象，清除它们并不会带来任何成本。（事实上，存在一个简单地保持对象活着的代价，大概是通过使用代数来摊销。）相反，在一个简单的引用计数收集器中，我可以很容易地想象它会花费O（n）来执行清理...

这并不明显对我来说如何推理这个时候设计算法..

来源

2010-09-20 10:14:04 pauldoo

我怀疑你可以假设the amortized costs该声明是O（1）。在实践中，这就是我所做的，而且我从未发现使我怀疑这种假设不正确的情况。

来源

2010-09-20 10:19:49 peSHIr

摊销成本当然只是O（1），因为它至少需要O（N）来分配对象。因此，即使收集器采用一次性O（N）清除它们，它已经被执行分配所需的先前O（N）操作“付费”。 – pauldoo 2010-09-20 10:23:58

我感兴趣的是该报表的最坏情况成本，而不是摊销成本。 – pauldoo 2010-09-20 10:24:29

@pauldoo：在最糟糕的情况下，垃圾收集器将决定是时候执行一个完整的集合并扫描每一个跟踪的对象，其中任何函数的成本都是无限的N. – 2010-09-20 20:05:18

垃圾收集运行时间成本的大O分析

回答

相关问题