Koks laiko rezultatas turi įterpimo, paieškos, skaitymo ir elementų ištrynimo operacijos masyve blogiausiu ir vidutiniu atveju?

Standartiniame iOS masyve (pvz., NSArray arba NSMutableArray) operacijų laiko charakteristikos yra maždaug tokios:

• Įterpimas:

  • Į masyvo pabaigą (append): vidutinis ir blogiausias atvejis — O(1) amortizuotas (jei nereikia atminties perdalymo).
  • Pradžioje arba viduryje: O(n), nes reikia perkelti elementus.

• Paieška (jei pagal indeksą): O(1), nes masyvas indeksuojamas.

• Skaitymas pagal indeksą: O(1).

• Ištrynimas:

  • Iš masyvo pabaigos: O(1).
  • Iš pradžios arba vidurio: O(n), dėl elementų perkėlimo.

Todėl, įterpimo ir ištrynimo operacijos viduryje arba pradžioje turi linijinę sudėtingumą, o prieiga ir įterpimas/ištrynimas pabaigoje — pastovų (amortizuotą) laiką.