Чӣ гуна вақтӣ мураккабии амали ворид кардани унсур ба оғози массиви динамикӣ ArrayList аст?

Вставка элемента баи оғоз дар массиви динамикӣ (масалан, ArrayList дар Java) дорои мураккабии вақт O(n) аст, ки дар он n шумораи элементҳо дар массив мебошад.

Ин ба он вобаста аст, ки вақте ки дар оғоз илова мекунед, ҳамаи элементҳои мавҷуда бояд як ҷой ба тарафи рост ҳаракат кунанд, то ҷой барои элементи нав кушода шавад. Процеси нусхабардории элементҳо худ вақтро дароз мекунад.

Масалан:

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

// Илова дар оғоз
list.add(0, 0); // ҳамаи элементҳоро ба тарафи рост ҳаракат медиҳад

Аз ин рӯ, илова кардан ба охир одатан тезтар аст (амортизатсияшуда O(1)), дар ҳоле ки ба оғоз — O(n).