垃圾收集運行時間成本的大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分析

回答

相關問題