Какова временная сложность вставки n элементов в конец массива?

Question

Я знаю, что вставка элемента в массив занимает постоянное время, скажем, c.

Что я пробовал:

для вставки n элементов time=c+c+c+.......n times =nc

Я хочу спросить, будет ли это большой O из n или o (1).

Answer 1

Да, для добавления n элементов требуется O (n) времени, но добавление отдельного элемента не является O (1). Это амортизируется O (1).

Любое данное добавление может потребовать O (n) времени само по себе, поскольку пространство текущего массива заполнено, поэтому его необходимо скопировать в другое, большее пространство.

Но если выделение нового пространства на постоянный коэффициент больше, чем один оригинала (часто используется 2), то стоимость копии амортизируется, так что среднее время на добавление, как вы говорите, постоянно, и n добавляет O (n).

Чтобы сделать это более понятным, рассмотрим случай, когда коэффициент равен 2, а начальный размер массива равен 1. Затем рассмотрим затраты на копирование, чтобы увеличить массив с размера 1 до размера, достаточного для хранения, 2 ^ k + 1 элементов для любого к> = 0. Этот размер 2 ^ (к + 1). Общие затраты на копирование будут включать в себя все копирование, чтобы стать таким большим в 2 раза:

1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = 2n - 1

Равенства связаны с базовой алгеброй. Результат O (n). Однако в самой последней копии содержится n = 2 ^ k элементов, что также равно O (n).

Answer 2

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

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