Vektörden öğeleri kaldırma işleminin en kötü durumda zaman karmaşıklığı nedir?

En kötü durumda, bir vektörden (C++'ta std::vector) öğeleri kaldırmak zaman karmaşıklığı O(n) olan bir işlemdir, burada n, kaldırma konumundan sonra vektördeki öğe sayısıdır. Bu, öğeleri kaldırdıktan sonra, tüm sonraki öğelerin boşluğu doldurmak için sola kaydırılması gerektiği anlamına gelir.

Örneğin, vektörün başındaki bir öğe kaldırılırsa, diğer tüm öğelerin bir pozisyon ileri kaydırılması gerekir, bu da O(n) işlem gerektirir.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // ilk öğeyi kaldırma
// tüm öğeler bir pozisyon sola kayar

Eğer sonundaki bir öğe kaldırılırsa, kaydırma gerekmez ve işlem O(1)’e daha yakın olur. Ama en kötü durumda — O(n).