Mekkora az időbeli komplexitása van egy elem törlésének egy tömbből?

Egy elem törlésének időbeli komplexitása egy tömbből attól függ, hogy hol található az elem, és hogy hogyan van megvalósítva a tömb.

• Ha index szerint kell törölni egy elemet, dinamikus tömbben (például, List Dart/Flutter-ben), a törlés után minden következő elem eltolódik, hogy kitöltse az üres helyet. Ez O(n) időbeli komplexitást eredményez, ahol n a törölt elem utáni elemek száma.

• Ha az utolsó elemet töröljük, az művelet O(1) idő alatt végrehajtható, mivel nincs szükség eltolódásra.

Példa Dart-ban:

List<int> numbers = [1, 2, 3, 4, 5];
numbers.removeAt(2); // eltávolítja a 2. indexű elemet (a szám 3)
// törlés után a 3. és 4. indexű elemek balra tolódnak

Általánosságban elmondható, hogy egy elem törlése egy tömbből O(n) időbeli komplexitású művelet.