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

მოწყობილობის ელემენტის წაშლის დროითი სირთულე დამოკიდებულია მასივის ტიპზე და წაშლის მეთოდზე:

• სტანდარტულ მასივში (მაგალითად, Array Swift-ში) ელემენტის წაშლა ინდექსით მოითხოვს ყველა შემდეგი ელემენტის მარცხნივ გადატანას, რათა შეივსოს "გაფუჭება". ეს იწვევს O(n) სირთულეს, სადაც n — წაშლილი ელემენტის შემდეგი ელემენტების რაოდენობა.

• თუ ბოლო ელემენტი წაიშლება, ოპერაცია ჩვეულებრივ ხორციელდება O(1)-ში, რადგან გადატანა საჭირო არ არის.

• დინამიური მასივების შემთხვევაში (მაგალითად, ArrayList Java-ში ან NSMutableArray Objective-C-ში) სიტუაცია მსგავსია — შუაში წაშლა მოითხოვს ელემენტების გადატანას.

მაგალითი:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // წაშლის 2-ინდექსიან ელემენტს (რიცხვი 3)
// წაშლის შემდეგ, ელემენტები 4 და 5 ერთი პოზიციით მარცხნივ გადაინაცვლებენ

საერთო ჯამში, მასივიდან ელემენტის წაშლა — დროითი სირთულე O(n) ოპერაციაა.