arrays — это Big-O оператора C ++ ‘delete [] Q;’ O (1) или O (n)?
Название говорит само за себя. Очень легкий вопрос. Я думаю, что это O (n), но хотел проверить до моего последнего завтрашнего дня.
Решение
Краткий ответ … это зависит.
Если Q указатель на массив объектов, которые имеют деструкторы, то delete[] Q нужно будет вызвать всех этих деструкторов. Это вызовет O (n) деструкторов, где n — количество элементов в массиве. С другой стороны, если Q указывает на массив объектов, которые не имеют деструкторов (например, intс или просто structs), тогда не нужно вызывать деструкторов, что занимает всего O (1) времени.
Теперь обратите внимание, что эти деструкторы не должны запускаться за O (1) раз каждый. Если объекты, скажем, std::vector объекты, то каждый деструктор, в свою очередь, должен уволить больше освобождения. Не зная больше о том, что это за объекты, все, что мы можем сказать, это то, что если будут вызваны деструкторы, то будет 0 вызванных деструкторов, если деструкторы тривиальны, а O (n) деструкторов вызваны иначе.
Но это игнорирует детали реализации того, как работает распределитель кучи. Возможно, что для освобождения блока памяти может потребоваться время O (log K), где K — общее количество выделенных блоков, или это может занять время O (1) независимо от того, сколько блоков памяти существует, или это может занять O (log log K) и т. Д. Не зная, как работает распределитель, вы, честно говоря, не можете быть уверены.
Короче говоря, если вы сосредоточены исключительно на работе, необходимой для очистки объектов перед передачей блока обратно в распределитель памяти, существуют O (n) деструкторов, вызываемых, если в сохраненных объектах есть деструкторы и 0 деструкторов, вызываемых иначе. Эти деструкторы могут занять нетривиальное количество времени для завершения. Затем есть стоимость повторного введения блока памяти обратно в распределитель памяти, что может занять отдельное количество времени.
Надеюсь это поможет!
Другие решения
Я согласен с этим, зависит, но давайте просто поговорим об освобождении X байтов памяти и не будем беспокоиться о деструкторах.
Некоторые распределители памяти хранят свободные списки для «маленьких» (от 1 до 500 байт) объектов. Вставка в список O (1). Если для всех потоков существует один свободный список, то он должен получить мьютекс. Получение мьютекса обычно включает в себя до 1000 «спинов», а затем, возможно, системный вызов (что очень дорого). У некоторых распределителей есть свободные списки для каждого потока, использующие локальное хранилище потока, поэтому они не получают мьютекс.
Для объекта среднего размера (от 500 до 60000 байт) многие распределители будут выполнять объединение блоков. То есть они проверяют, свободны ли смежные блоки, и объединяют 2 или 3 свободных блока, чтобы сделать 1 больший свободный блок. Коалесцирование — это O (1), но опять же ему нужно приобрести мьютекс.
Для больших блоков некоторые распределители получают память, используя системный вызов. Таким образом, освобождение памяти также является системным вызовом.
detector