Какова временная сложность распределения динамической памяти с помощью new, malloc и т.д.? Я очень мало знаю о том, как реализованы распределители памяти, но я полагаю, что ответ заключается в том, что это зависит от реализации. Поэтому, пожалуйста, ответьте на некоторые из наиболее распространенных случаев/реализаций.
Изменить: Я смутно помню, что распределение кучи неограниченно в худшем случае, но меня действительно интересует средний/типичный случай.
Одна из вещей, которые вы должны понимать при работе с нотацией O, заключается в том, что часто очень важно понять, что такое n. Если n что-то связано с чем-то, что вы можете контролировать (например: количество элементов в списке, который вы хотите отсортировать), тогда имеет смысл внимательно смотреть на него.
В большинстве реализаций кучи ваше n - количество смежных кусков памяти, которыми управляет менеджер. Это явно не что-то обычно под контролем клиента. Единственный n, на котором клиент действительно контролирует, - это размер куска памяти, который она хочет. Часто это не имеет никакого отношения к количеству времени, которое занимает распределитель. Большое значение n может быть так же быстро выделено, как маленькое n, или это может занять гораздо больше времени, или оно может быть даже невосприимчивым. Все это может измениться для одного и того же n в зависимости от того, как вошли предыдущие распределения и освобождения от других клиентов. Так что, если вы не используете кучу, тогда правильный ответ заключается в том, что он не является детерминированным.
Вот почему программисты в реальном времени стараются избегать динамического распределения (после запуска).
Сложность времени для распределителя кучи может быть разной в разных системах, в зависимости от того, для чего они могут оптимизировать.
В настольных системах распределитель кучи, вероятно, использует смесь различных стратегий, включая кэширование недавних распределений, списки просмотра для общих размеров размещения, бункеры блоков памяти с определенными характеристиками размера и т.д., чтобы попытаться сохранить время распределения, но также сохранить фрагментация управляема. См. Примечания к реализации Doug Lea malloc для обзора различных методов, которые используются: http://g.oswego.edu/dl/html/malloc.html
Для более простых систем может использоваться стратегия первого соответствия или наилучшего соответствия, при этом свободные блоки хранятся в связанном списке (что даст время O (N), когда N будет числом свободных блоков). Но более сложная система хранения, такая как дерево AVL, может быть использована для поиска свободных блоков в времени O (log N) (http://www.oocities.org/wkaras/heapmm/heapmm.html).
Система реального времени может использовать распределитель кучи, такой как TLSF (двухуровневый разделительный набор), который имеет стоимость распределения O (1): http://www.gii.upv.es/tlsf/
Я бы подумал, что в общем случае это O (n), где n - количество доступных блоков памяти (так как вы должны сканировать доступные блоки памяти, чтобы найти подходящий).
Сказав это, я видел оптимизацию, которая может ускорить ее работу, в частности, поддерживая несколько списков доступных блоков в зависимости от их диапазонов размеров (так что блоки меньше 1k находятся в одном списке, блоки от 1k до 10k находятся в другом списке и т.д.).
Это все равно O (n), однако, с меньшим n.
Мне было бы интересно увидеть ваш источник, что есть распределение кучи, которое неограничено (если вы это понимаете, это может занять бесконечно).
Просто проверьте, как работают типовые распределители.
Распределитель bump-the-pointer работает в O (1), и в нем есть небольшой "1".
Для распределителя с разделенным хранилищем выделение k байтов означает "вернуть первый блок из списка (n)", где List (n) - это список блоков из n байтов, где n >= k. Он может найти, что List (n) пуст, так что блок из следующего списка (List (2n)) должен быть разделен на оба результирующих блока из n байтов, которые помещаются в List (n), и этот эффект может пульсировать по всем availlable размерам, делая сложность O (ns), где ns - количество различных размеров availlable, и ns = log (N), где N - размер наибольшего размера блока availlable, так что даже это было бы мало. В большинстве случаев, особенно после того, как было выделено и освобождено несколько блоков, сложность O (1).
Только два замечания:
TLSF - это O (1) в том смысле, что он не имеет ни одного цикла; и управляет до 2 Гб. Хотя это действительно сложно поверить, просто проверьте код.
Неверно, что политика "наилучшего соответствия" (найти узкий блок) является наиболее подходящей для добиться небольшой фрагментации. Напротив, это не так просто, чтобы продемонстрировать это утверждение, на самом деле оно официально не доказано, но есть много свидетельств, которые идут в этом направлении. (хорошая тема для исследования).