Kuidas hinnata elementide eemaldamise operatsiooni ajakulutust massiivist?

Elementi eemaldamise ajakulu massiivist sõltub massiivi tüübist ja eemaldamise meetodist:

• Tavalises massiivis (näiteks Array Swiftis) nõuab elemendi eemaldamine indeksi järgi kõigi järgneva elemendi vasakule nihutamist, et täita "auk". See viib O(n) ajakuluni, kus n on eemaldatud elemendi järgnevad elemendid.

• Kui eemaldatakse viimane element, tehakse operatsioon tavaliselt O(1)-s, kuna nihutamist ei ole vaja.

• Dynaamilistes massiivides (näiteks ArrayList Java-s või NSMutableArray Objective-C-s) on olukord sarnane — keskelt eemaldamine nõuab elementide nihutamist.

Näide:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // eemaldab indeksi 2 elemendi (number 3)
// Pärast eemaldamist nihkuvad elemendid 4 ja 5 ühe positsiooni vasakule

Üldiselt on massiivist elemendi eemaldamine operatsioon, mille ajakulu on O(n).