Какова временная сложность функции realloc в C? - PullRequest
Новая
       36

Какова временная сложность функции realloc в C?

0 голосов
/ 23 мая 2018

У меня вопрос: какова временная сложность функции realloc?Например, у меня есть массив целых чисел: a [10].Конечно, массив был динамически размещен таким образом => 

int *a = (int*)malloc(10*sizeof(int));

И затем я хочу изменить размер этого массива до 11, чтобы вставить дополнительное значение в массив a, поэтому я делаю =>

a = (int*)realloc(a, 11*sizeof(int));

Мой вопрос: какова временная сложность перераспределения?Действительно ли realloc просто добавляет дополнительную ячейку в массив, а затем принимает O (1), или он повторно регистрирует весь массив a, добавляет дополнительную 11-ю ячейку и возвращает массив нового размера, и в этом случае временная сложность этого действия равна O(п)?Какое предположение верно?

Ответы [ 2 ]

0 голосов
/ 23 мая 2018

realloc эквивалентно: 

void *
realloc(void *old, size_t new_size)
{
    size_t old_size = internal_function_that_knows_old_size(old);
    void *new = malloc(new_size);
    if (new == NULL)
        return NULL;
    size_t sz = old_size;
    if (new_size < old_size)
        sz = new_size;
    memcpy(new, old, sz);
    free(old);
    return new;
}

Возможно realloc иметь оптимизации, которые в некоторых ситуациях делают это быстрее, но я почти уверен, что эти оптимизации невозможно выполнитьвсегда работает, поэтому запасной вариант всегда будет функцией, которая делает что-то похожее на вышеописанное, поэтому вы должны рассмотреть это как наихудший случай.

Теперь, когда речь идет о сложности времени, в стандарте нет ничего, что требуетmalloc или free имеют любое разумное поведение, поэтому возможно, что они будут доминировать во время выполнения этой функции (или internal_function_that_knows_old_size будет), но, поскольку эти биты системы обычно довольно хорошо написаны, это маловероятно.Доминирующей частью (по крайней мере, для больших n, где сложность интересна) будет memcpy.

Так что при некоторых разумных допущениях realloc должно быть O (n) (где n - этостарый или новый размер выделения в зависимости от того, что меньше).

0 голосов
/ 23 мая 2018

Во-первых, ваш код (в оригинальной форме вашего вопроса) неверен.По крайней мере, оно должно быть 

a = realloc(a, 11*sizeof(int));

(в противном случае вы, вероятно, будете иметь неопределенное поведение в обычном случае, когда sizeof(int) больше единицы).КСТАТИ realloc не следует бросать в C.

Тогда ваш вопрос

Какова временная сложность функции realloc в C?

нет смысла, если вы не говорите о какой-то конкретной функции realloc, реализацию которой вы знаете.

Обратите внимание, что realloc допускается сбой.Вот его эффективная, но бесполезная реализация с постоянным временем (см. Также этот ответ; это стандарт, соответствующий realloc, который следует за буквой, но не по духу, стандарта n1570): 

void *realloc( void *ptr, size_t new_size ) { 
  errno = ENOMEM;
  return NULL;
}

Наконец, на практике вы можете считать malloc и realloc как-то дорогостоящими операциями (типичное время выполнения может составлять несколько микросекунд, поэтому в тысячи раз медленнее, чем сложение).), и во многих случаях вы не хотите realloc на каждом цикле.Так что вы скорее будете использовать некоторый геометрический рост для realloc (например, здесь )

Realloc просто добавляет дополнительную ячейку в массив, а затем занимает O (1)или он переписывает весь массив a, добавляет дополнительную 11-ю ячейку и возвращает массив нового размера, и в этом случае временная сложность этого действия составляет O (n)?

Может произойти и то и другое.Вы можете себе представить, что malloc хранит где-то выделенный размер (округленный до реализации ...) и в хороших случаях realloc возвращает тот же указатель (так что O (1)), а в менее удачных случаях необходимо скопироватьзона памяти в другом месте.Не зная вашей конкретной реализации (из malloc, realloc, free), вы не сможете узнать, что является наиболее распространенным случаем или их вероятностным распределением.Кстати, кажется, что реализация realloc, которая всегда копирует данные (или дает сбой), соответствует стандарту (но неэффективно).Если вам нужно узнать больше, вам следует протестировать.

Наконец, многие реализации стандартной библиотеки C бесплатное программное обеспечение (например, GNU libc , musl-libc , ...) и вы можете изучить их исходный код malloc, free, realloc (выше операционная система примитивы - обычно системные вызовы - увеличение виртуального адресного пространства ; в Linux что-то вроде mmap (2) )

...