Jak odhadnout časovou složitost operace odstranění prvku z pole?

Časová složitost odstranění prvku z pole závisí na typu pole a způsobu odstranění:

• U standardního pole (například Array ve Swiftu) vyžaduje odstranění prvku podle indexu posunutí všech následujících prvků vlevo, aby se zaplnila "díra". To vede k časové složitosti O(n), kde n je počet prvků po odstraněném.

• Pokud je odstraněn poslední prvek, operace se obvykle provádí za O(1), protože posun není potřeba.

• U dynamických polí (například ArrayList v Javě nebo NSMutableArray v Objective-C) je situace podobná — odstranění uprostřed vyžaduje posun prvků.

Příklad:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // odstraní prvek na indexu 2 (číslo 3)
// Po odstranění se prvky 4 a 5 posunou o jednu pozici vlevo

Obecně platí, že odstranění prvku z pole je operace s časovou složitostí O(n).