Почему добавление неизменяемых контейнеров в цикле O(n²)?

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

string = ""
repeat n times:
    string = string + "X"

Почему это?


performance big-o language-agnostic
person Veedrac    schedule 10.06.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Добавление неизменного непрерывного контейнера длиной A к контейнеру длиной B обычно занимает O(A+B) времени. Это связано с тем, что полученный контейнер нужно будет построить заново, и его длина будет равна A+B.

Рассмотрим ith добавление данного цикла. Строка будет иметь длину i-1, а вы добавите строку длиной 1. Результирующая строка и, следовательно, требуемое время пропорциональны i.

Таким образом, мы имеем общую стоимость:

1 + 2 + 3 + 4 + 5 + ... + n-2 + n-1 + n

= ∑i from i=1 to i=n

= ½n·(n+1)

= ½n² + ½n

который имеет порядок O(n²).

Причина, по которой они указаны как непрерывные контейнеры, заключается в том, что некоторые несмежные неизменяемые контейнеры (например, двоичные деревья) могут просто ссылаться на другие неизменяемые контейнеры, а не копировать их, что может увеличить скорость добавления.

person Veedrac    schedule 10.06.2014