Одна из вещей, которую вы должны понимать при работе с нотацией O, заключается в том, что часто очень важно понять, что такое n. Если n что-то связано с чем-то, что вы можете контролировать (например: количество элементов в списке, который вы хотите отсортировать), тогда имеет смысл внимательно смотреть на него.
В большинстве кучевых реализаций n - это количество смежных кусков памяти, которыми управляет менеджер. Это, безусловно, не что-то обычно под контролем клиента. Единственный n клиент действительно имеет контроль над размером куска памяти, который она хочет. Часто это не имеет никакого отношения к количеству времени, которое занимает распределитель. Большой n может быть так же быстро выделен, как маленький n, или это может занять гораздо больше времени, или оно может быть даже невосстановимым. Все это может измениться для тех же n в зависимости от того, как вступили предыдущие распределения и освобождения от других клиентов. Так что, если вы не используете кучу, то правильный ответ заключается в том, что он не является детерминированным.
Вот почему программисты в реальном времени пытаются избежать динамического распределения (после запуска).
Динамическая память обычно требуется, когда количество обрабатываемых данных не может быть определено до времени выполнения. Распределенная память, как правило, переводится во время обработки. Таким образом, речь идет не только о времени выполнения распределения, но необходимость иметь память кучи не возникает в первую очередь. – doppelfish 2008-12-31 17:50:20
Ну, это действительно необходимо, когда ** верхний предел суммы ** не может быть разумно определен до выполнения.Если вы можете ограничить количество во время компиляции, и у вас достаточно ОЗУ, вы можете просто выделить максимум. – 2010-03-23 13:11:24