Junior — Middle
Slice-ის გამოყენებით მასივის ბოლოს ელემენტის დამატების ოპერაციის დროის სირთულე რა არის?
sobes.tech AI
პასუხი AI-სგან
Go-ში, ელემენტის დამატება სლაისის ბოლო ნაწილში (append) აქვს ამორტიზირებული დროის სირთულე O(1).
განმარტება:
-
თუ სლაისს აქვს საკმარისი მოცულობა (
capacity), ელემენტის დამატება ხდება უბრალოდ შემდეგ თავისუფალ ინდექსზე დაწერით — ეს ოპერაცია არის დროის კონსტანტული. -
თუ მოცულობა არ არის საკმარისი, გამოყოფილი იქნება ახალი, უფრო დიდი მასივი, ძველი ელემენტები გადაიტანება და დაემატება ახალი — ეს ოპერაცია იღებს O(n) დრო, სადაც n არის მიმდინარე სლაისის ზომა.
თუმცა, რადგან ასეთი გადანაწილებები არ ხდება ყოველ დამატებაზე, არამედ პერიოდულად, დამატების საშუალო (ამორტიზირებული) სირთულე რჩება O(1).