Kāda ir dinamiskā masīva ArrayList elementa ievietošanas operācijas laika sarežģītība?

Dinamis masīva elementa pie sākuma (piemēram, Java ArrayList) ir ar laika sarežģītību O(n), kur n ir elementu skaits masīvā.

Tas ir tāpēc, ka, ievietojot sākumā, visi esošie elementi ir jānovieto vienu pozīciju pa labi, lai atbrīvotu vietu jaunajam elementam. Pašu elementu kopēšanas process aizņem lineāru laiku.

Piemērs:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Ievietošana sākumā
list.add(0, 0); // pārvieto visus elementus pa labi

Tādēļ, pievienošana beigās parasti ir ātrāka (amortizēti O(1)), bet sākumā — O(n).