რამდენად არის დროის სირთულე დინამიური მასივში ელემენტის დამატების ოპერაციას?

დინამიური მასივის ელემენტის დამატება ჩვეულებრივ აქვს ამორტიზირებული დროის სირთულე O(1).

განმარტება:

• თუ მასივში თავისუფალი ადგილი არსებობს, ელემენტი დამატებულია კონსტანტულ დროში.
• თუ ადგილი არ არის, მასივი გამოყოფს ახალი, უფრო დიდი მეხსიერების ბლოკს (საშუალოდ ორჯერ დიდს), კოპირებს ძველ ელემენტებს და დამატებს ახალს.

მიუხედავად იმისა, რომ გაფართოების ოპერაცია იღებს O(n) დროს, ის იშვიათად ხდება, ამიტომ დამატების საშუალო (ამორტიზირებული) სირთულე რჩება O(1).

მაგალითი Go-ს slices-ის გამოყენებით:

var arr []int
arr = append(arr, 10) // ელემენტის დამატება

append ავტომატურად გააფართოებს slices-ს საჭიროების შემთხვევაში.