Ինչպե՞ս է ժամանակային բարդությունը ArrayList տեսակի զանգվածի վերջում տարր ավելացնելու գործողության համար։

ArrayList տիպի զանգվածի վերջում տարր ավելացնելու ժամանակային բարդությունը միջինում կազմում է O(1) — ամորտիզացված հաստատուն ժամանակ:

Սա տեղի է ունենում, քանի որ ArrayList-ը պահում է տարրերը հաստատված չափի զանգվածում: Երբ ավելացնում ենք տարր և զանգվածում կա ազատ տեղ, տարրը պարզապես տեղադրվում է հաջորդ բջիջում:

Եթե սակայն զանգվածը լրացված է, կատարվում է ընդլայնման օպերացիա — ստեղծվում է նոր ավելի մեծ զանգված և բոլոր տարրերը պատճենվում են դրան: Այս օպերացիան տևում է O(n) ժամանակ, որտեղ n տարրերի քանակն է:

Օրինակ:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Երբ զանգվածի ծավալը հասնում է, կատարվում է ընդլայնում — O(n)

Այսպիսով, ավելացման միջին բարդությունը — O(1), բայց ամենավատ դեպքերում — O(n).