Время выполнения инициализации массива с нулевым заполнением

Question

Если бы я должен был определить следующий массив, используя синтаксис инициализации нулевого заполнения в стеке:

int arr[ 10 ] = { 0 };

... время выполнения постоянное или линейное?

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

Если бы вы могли также указать причину, а не только это, заказ ххх был бы потрясающим!

Answer 1

Время выполнения линейно по размеру массива.

Чтобы понять почему, вот пример реализации memset, которая инициализирует массив произвольным значением. На уровне ассемблера это ничем не отличается от того, что происходит в вашем коде.

void *memset(void *dst, int val, size_t count) {
    unsigned char *start = dst;
    for (size_t i = 0; i < count; i++)
        *start++ = value;
    return dst;
}

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

Answer 2

Это на самом деле верхушка вопроса айсберга. На самом деле вы спрашиваете, каков порядок (Big Oh) инициализации массива. По сути, код проходит по каждому элементу массива и устанавливает их в ноль. Вы можете написать цикл for, чтобы сделать то же самое.

Порядок величины этого цикла равен O(n), то есть время, проведенное в цикле, увеличивается пропорционально количеству инициализируемых элементов.

Если аппаратное обеспечение поддерживает инструкцию, которая говорит, что все байты должны быть установлены из положения X в Y в ноль, и эта инструкция работает в M циклах инструкций, и M никогда не изменяется независимо от количества байтов, устанавливаемых в ноль, то это будет порядка k, или O(k).

В общем, O(k), вероятно, называется постоянным временем, а O (n) - линейным.