Ako odhadnúť časovú zložitosť operácie odstránenia prvku z poľa?

Časová zložitosť odstránenia prvku z poľa závisí od typu poľa a spôsobu odstránenia:

• V štandardnom poli (napríklad Array v Swift) vyžaduje odstránenie prvku podľa indexu posunutie všetkých nasledujúcich prvkov doľava, aby sa zaplnila "diera". To vedie k časovej zložitosti O(n), kde n je počet prvkov po odstránenom.

• Ak je odstránený posledný prvok, operácia sa zvyčajne vykonáva za O(1), pretože posun nie je potrebný.

• V prípade dynamických polí (napríklad ArrayList v Jave alebo NSMutableArray v Objective-C) je situácia podobná — odstránenie uprostred vyžaduje posun prvkov.

Príklad:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // odstráni prvok na indexe 2 (číslo 3)
// Po odstránení sa prvky 4 a 5 posunú o jednu pozíciu doľava

Všeobecne platí, že odstránenie prvku z poľa je operácia s časovou zložitosťou O(n).