Aká je časová zložitosť operácie odstránenia prvku z poľa?

Časová zložitosť odstránenia prvku z poľa závisí od toho, kde sa prvok nachádza, a od toho, ako je pole implementované.

• Ak je potrebné odstrániť prvok podľa indexu, v dynamickom poli (napríklad, List v Dart/Flutter), po odstránení sa všetky nasledujúce prvky posunú, aby sa zaplnil voľný priestor. To vedie k časovej zložitosti O(n), kde n je počet prvkov po odstránenom.

• Ak odstránite posledný prvok, operácia sa vykoná v O(1), pretože nie je potrebné posúvanie.

Príklad v Dart:

List<int> numbers = [1, 2, 3, 4, 5];
numbers.removeAt(2); // odstráni prvok na indexe 2 (číslo 3)
// po odstránení sa prvky na indexoch 3 a 4 posunú doľava

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