Ինչպե՞ս է ժամանակային բարդությունը դինամիկ զանգված 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):