Ամենափոքր ժամանակային բարդությունը ինչ է զանգվածի սկզբին տարր ավելացնելու գործողության համար?

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

Սա կապված է այն բանի հետ, որ սկզբին ավելացնելու համար անհրաժեշտ է տեղափոխել բոլոր առկա տարրերը աջ, որպեսզի ազատ տեղ ստեղծվի նոր տարրի համար: Դինամիկ զանգվածներում (օրինակ, Swift Array) այս գործընթացը պահանջում է պատճենում կամ տեղափոխում տարրեր, ինչը ժամանակ է պահանջում, proporcional առ տարրերի քանակին:

Օրինակ՝

var array = [2, 3, 4]
array.insert(1, at: 0) // ավելացնում ենք 1 սկզբին
print(array) // [1, 2, 3, 4]

Այստեղ, երբ ավելացնում ենք 1-ը, բոլոր տարրերը տեղափոխվում են աջ մեկ դիրք։