7
Название не требует пояснений. Очень простой вопрос. Я думаю, что это O (n), но хотелось проверить до моего финального завтрашнего дня.Is Big-O оператора C++ 'delete [] Q;' O (1) или O (n)?
A
ответ
16
Короткий ответ ... это зависит.
Если Q является указателем на массив объектов с деструкторами, то delete[] Q необходимо будет вызвать все эти деструкторы. Это вызовет деструкторы O (n), где n - количество элементов в массиве. С другой стороны, если Q указывает на массив объектов, у которых нет деструкторов (например, int s или просто struct s), то не нужно вызывать деструкторов, что занимает только время O (1).
Теперь обратите внимание, что эти деструкторы не должны запускаться в течение O (1) раз. Если объекты являются, скажем, std::vector объектами, то каждый деструктор, в свою очередь, должен уволить больше освобождений. Не зная больше о том, что представляют собой эти объекты, все, что мы можем сказать, состоит в том, что если будут вызваны деструкторы, то будут вызваны деструкторы 0, если деструкторы тривиальны и O (n) деструкторы называются иначе.
Но это игнорирует детали реализации того, как работает распределитель кучи. Возможно, что освобождение блока памяти может занять время O (log K), где K - общее количество выделенных блоков, или может занять время O (1) независимо от того, сколько блоков памяти есть, или может потребоваться O (log log K) и т. Д. Не зная, как работает распределитель, вы, честно говоря, не можете быть уверены.
Короче говоря, если вы фокусируетесь исключительно на работе, требуемой для очистки объектов, прежде чем передать блок обратно в распределитель памяти, есть вызванные деструкторы O (n), если в хранимых объектах есть деструкторы и 0 деструкторов, вызываемые иначе. Эти деструкторы могут потребовать нетривиального количества времени для завершения. Тогда есть стоимость повторного ввода блока памяти в распределитель памяти, который может занять свое собственное время.
Надеюсь, это поможет!
+1
@ Ethan Баррон теперь записывает это на чистую бумагу. положите его под рубашку.когда раздаются вопросники, сделайте быстрый шаг и возьмите бумагу под рубашку под вопросом. удачи. –
+1
Я хотел бы добавить что-то важное, что многие пропустили. Объекты, которые содержит массив, не должны быть определены * деструкторами. Важно то, что деструктор (либо определенный, либо по умолчанию) * тривиальный *. То есть, если класс имеет «вектор» в качестве члена, тогда деструктор по умолчанию является нетривиальным и будет запущен, даже если нет деструктора, явно определенного – Duncan
+0
@templatetypedef. Это отличный ответ, большое вам спасибо. –
2
Я согласен с этим, но давайте просто поговорим о освобождении X байтов памяти и не беспокоиться о деструкторах.
Некоторые распределители памяти сохраняют свободные списки для «маленьких» (от 1 до 500 байт) объектов. Вставка в список - O (1). Если для всех потоков есть один свободный список, ему необходимо получить мьютекс. Приобретение мьютекса обычно включает в себя пару 1000 «спинов», а затем, возможно, системный вызов (что очень дорого). В некоторых распределителях есть свободные списки для потока с использованием локального хранилища потоков, поэтому их нет для мьютекса.
Для среднего размера (от 500 до 60000 байт) большого количества распределителей будет выполняться блок-коалесценция. То есть они проверяют, являются ли смежные блоки также бесплатными, и они объединяют 2 или 3 свободных блока, чтобы сделать 1 более свободный свободный блок. Коалесцирование - это O (1), но опять же ему необходимо получить мьютекс.
Для больших блоков некоторые распределители получают память с помощью системного вызова. Таким образом, освобождение памяти также является системным вызовом.
Смежные вопросы
- 1. Большой O-O (N^2) или O (N^2 + 1)?
- 2. Это O (n^2) или O (1)?
- 3. Перемещение бит O (1) или O (n)?
- 4. Сложность Время O (n) или O (n (n + 1)/2)
- 5. Is string.ElementAt() O (1)?
- 6. Выбор O (n) над O (1), когда для всех n, O (1) быстрее, чем O (n)?
- 7. На практике добавляется связанный список O (N) или O (1)?
- 8. clojure subvec O (n) вместо O (1)?
- 9. Is O (LogN) == O (3LogN)?
- 10. Который больше: O (n * logn) или O (1)?
- 11. Сборники Java: TreeMap.size() и TreeSet.size(): O (1) или O (n)?
- 12. Доступ к DataRowCollection.Count O (1) или O (n) в DataTable
- 13. Является ли этот код O (N) или O (1)
- 14. Сумма порядка O (1) + O (2) + .... + O (n)
- 15. Не следует вставлять только O (n) не O (1) или O (n) вставлять в несвязанный список?
- 16. Улучшение движения деления от O (n) до O (1)
- 17. C++ Разбиение списка в O (n) вместо O (1)
- 18. Как может быть алгоритм O (n) также O (n^2), O (n^1000000), O (2^n)?
- 19. Практическое различие между O (n) и O (1 + n)?
- 20. ListBox.FindString, что является наихудшим временем выполнения? O (n), O (n log n), O (1)?
- 21. Является ли сложность этого кода O (n^2) или O (n^2 * n^(1/2))?
- 22. циклической перестановкой в O (1) пространство и O (N) времени
- 23. - это выражение O (n^2) или O (n^3)?
- 24. Примеры алгоритмов, которые имеют O (1), O (n log n) и O (log n) сложности
- 25. Is 2^2n = O (2^n)?
- 26. Является большим o для следующего O (n^2 * log (n)) или O (n^3 * log (n))
- 27. Сложность времени O (N) или O (Log N)?
- 28. Is 2^(2n) = O (2^n)
- 29. Вычисление ноты Not-O, O (n) * O (log n) = O (n log n)
- 30. O (log_2 (n)) = O (log_10 (n))?
Я дам вам подсказку: 'std :: string :: ~ string()' –
Какой тип 'Q'? –
Близко связанный: http://stackoverflow.com/q/16420357/179910 –