Динамикалык массив ArrayListтин башында элементти кошуу операциясынын убакыттык татаалдыгы кандай?

Динамик массивге (мисалы, Javaда ArrayList) элементти башында кошуу убакыттык татаалдыгы 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).