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

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

Ներկայացում:

• Եթե զանգվածում ազատ տեղ կա, տարրն ավելացվում է հաստատուն ժամանակով:
• Եթե տեղ չկա, զանգվածը հատկացնում է նոր ավելի մեծ հիշողության բլոկ (հաճախ երկու անգամ մեծ), պատճենում է հին տարրերը և ավելացնում նորին:

Չնայած ընդլայնման գործողությունը տևում է O(n), այն տեղի չի ունենում հաճախ, ուստի ավելացման միջին (ամորտիզացված) բարդությունը մնում է O(1):

Օրինակ Go լեզվով slices-ների հետ:

var arr []int
arr = append(arr, 10) // տարր ավելացնել

append-ը ավտոմատ կերպով ընդլայնում է slices-ը անհրաժեշտության դեպքում։