Когда рассуждение о стоимости выполнения во время сбора мусора, какова стоимость оператора, такого как myList = null; с точки зрения «n» (количество элементов в списке)? Для аргументации рассмотрите список как односвязный список ссылочных типов без необходимости завершения.Big O анализ затрат времени на сборку мусора
В целом, я ищу любую информацию о том, как затраты времени исполнения могут быть проанализированы на языке с GC.
Моя собственная мысль состоит в том, что стоимость может быть либо O (1), либо O (n) в зависимости от реализации коллектора. В сборщике меток и разметки недоступные объекты просто не будут достигнуты, поэтому я мог бы предположить, что не было затрат, связанных с их очисткой. (Infact существует постоянная стоимость, просто сохраняя объекты живыми, предположительно амортизированными с использованием поколений.) И наоборот, в простом подсчете счетного коллектора я легко мог себе представить, что он стоил O (n) для очистки ...
Это не очевидно мне как рассуждать об этом при разработке алгоритмов ..
Я подозреваю, что вы можете считать the amortized costs этого утверждения равным O (1). На практике это то, что я делаю, и я никогда не находил ситуации, из-за которой я подозревал, что это предположение неверно.
Амортизируемые затраты, безусловно, равны O (1), поскольку для размещения объектов в первую очередь потребовалось бы O (N). Таким образом, даже если сборщик берет один O (N), чтобы очистить их, он уже был «оплачен» предыдущими операциями O (N), необходимыми для выполнения распределений. – pauldoo
Меня интересует наихудшая стоимость этого заявления, а не амортизированная стоимость. – pauldoo
@pauldoo: В худшем случае сборщик мусора решит, что пришло время выполнить полную сборку и сканирование по каждому отслеживаемому объекту, стоимость которого не ограничена никакими функциями N. –