Защо добавянето на неизменни контейнери в цикъл е 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.

Помислете за _5-то добавяне на дадения цикъл. Низът ще бъде с дължина 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