Jak ocenić złożoność czasową operacji usunięcia elementu z tablicy?

Złożoność czasowa usunięcia elementu z tablicy zależy od typu tablicy i metody usuwania:

• W standardowej tablicy (np. Array w Swift) usunięcie elementu po indeksie wymaga przesunięcia wszystkich kolejnych elementów w lewo, aby wypełnić "lukę". To prowadzi do złożoności O(n), gdzie n to liczba elementów po usuniętym.

• Jeśli usuwany jest ostatni element, operacja zwykle jest wykonywana w O(1), ponieważ nie wymaga przesuwania.

• W przypadku dynamicznych tablic (np. ArrayList w Java lub NSMutableArray w Objective-C) sytuacja jest podobna — usunięcie z środka wymaga przesunięcia elementów.

Przykład:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // usuwa element na indeksie 2 (liczba 3)
// Po usunięciu elementy 4 i 5 przesuwają się o jedną pozycję w lewo

W związku z tym, ogólnie rzecz biorąc, usunięcie elementu z tablicy to operacja o złożoności czasowej O(n).