მასივები და დინამიური მასივები

მასივი ყველა ენაში ყველაზე ხშირად გამოყენებადი მონაცემთა სტრუქტურაა. თუ ზუსტად იცი, რაში არის ის კარგი და რაში ცუდი, უწყინარი სახის ნელ კოდს აირიდებ.

დამწყები⏱ 10 წთ

←ეყრდნობა

0სირთულე და ზრდის ტემპიpush_back-ის საშუალო O(1) არის Big-O შეფასება ბევრ ოპერაციაზე ერთად.

გზას უხსნის→

1ჰეშ-ცხრილები: set და mapჰეშ-ცხრილი არის კალათების მასივი, რომელსაც გასაღების ჰეშით ვინდექსავთ.1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაპრეფიქსული ჯამები მეორე მასივია, სადაც ნებისმიერი შუალედის ჯამი ორი O(1) წვდომაა.2მარტივი სორტირებებიყველა მარტივი სორტირება ელემენტებს ადგილზე ცვლის ერთი მასივის შიგნით.2დათვლითი სორტირებადათვლითი სორტირება გასაღებებს პირდაპირ მასივის ინდექსებად იყენებს.3ბმული სიებიბმული სია მასივის O(1) ინდექსაციას ცვლის ნებისმიერ ადგილას O(1) ჩასმაზე.3სტეკი (LIFO) და გამოსახულების გამოთვლასტეკი არის დინამიური მასივი, რომელიც მხოლოდ ბოლოში ამატებს და ბოლოდან იღებს.5ორობითი გროვა და პრიორიტეტული რიგიგროვა მასივში ცხოვრობს: i-ს შვილები 2i+1 და 2i+2 ადგილებზე არიან.6გრაფის წარმოდგენამოსაზღვრე წვეროთა სია დინამიური მასივების მასივია, თითო ყოველ წვეროზე.9უსგ და ერატოსთენეს საცერისაცერი ბულის მასივია, რომელსაც თავად რიცხვები ინდექსავს.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01მეხსიერების ერთი ბლოკი

მასივი ელემენტებს ინახავს გვერდიგვერდ, მეხსიერების ერთ უწყვეტ ბლოკში. ყველა ელემენტი ერთი ზომისაა, მაგალითად int-ისთვის 4 ბაიტი.

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

a[i]-ის მისამართი = base + i × size

ერთი გამრავლება და ერთი შეკრება, სულერთია i 3-ია თუ 3 მილიონი. ეს არის პირდაპირი წვდომა O(1)-ში, მასივის ზესძალა.

უწყვეტ მეხსიერებას მეორე უპირატესობაც აქვს: როცა პროცესორი a[i]-ს კითხულობს, მის მეზობლებსაც ქეშში ტვირთავს, ამიტომ მასივის მარცხნიდან მარჯვნივ გავლა პრაქტიკაში ძალიან სწრაფია.

02სისუსტე: შუაში ჩასმა

რადგან ელემენტები გვერდიგვერდ უნდა დარჩნენ, გამოსაყენებელი ცარიელი ადგილი არ არსებობს. i ინდექსზე მნიშვნელობის ჩასასმელად i-დან ბოლომდე ყველა ელემენტი ჯერ ერთი ადგილით მარჯვნივ უნდა გადაინაცვლოს. შუიდან წაშლა სარკისებური სურათია: ხვრელის შემდეგ ყველაფერი მარცხნივ ინაცვლებს.

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

დაულაგებელ მასივში მნიშვნელობის ძებნაც O(n)-ია: ელემენტები სათითაოდ უნდა ნახო. იაფად მხოლოდ მასივის ბოლოს შეცვლაა შესაძლებელი, ამიტომაა ყველაზე ხშირი ოპერაცია ბოლოში დამატება.

03დინამიური მასივები: ზომა და ტევადობა

ფიქსირებული მასივი ვერ იზრდება. დინამიური მასივი (C++ vector, Java ArrayList, Python list) ზრდის ილუზიას ორი რიცხვით ქმნის:

ზომა (size): რამდენი ელემენტი შეინახე
ტევადობა (capacity): რამდენი ეტევა მის მიერ გამოყოფილ ბლოკში

სანამ size < capacity, push_back უბრალოდ შემდეგ თავისუფალ უჯრაში წერს: O(1). როცა ბლოკი ივსება, ვექტორი ორჯერ დიდ ახალ ბლოკს გამოყოფს, ყველა ელემენტს იქ აკოპირებს, ძველს ათავისუფლებს და მერე წერს. ეს ერთი push O(n) ღირს.

თუ საბოლოო ზომა წინასწარ იცი, გამოიძახე reserve(n) და კოპირება საერთოდ არ დასჭირდება. და ფრთხილად: გადანაწილების შემდეგ ვექტორში არსებული ძველი მიმთითებლები და იტერატორები უკვე გათავისუფლებულ მეხსიერებაზე მიუთითებს.

04ამორტიზებული O(1): რატომაა გაორმაგება იაფი

ზოგი push O(n) ღირს. ნიშნავს ეს, რომ push_back ნელია? უარესი ცალკეული ოპერაციის ნაცვლად შეხედე n push-ის ჯამურ ღირებულებას.

კოპირება მხოლოდ მაშინ ხდება, როცა ზომა ორის ხარისხს გადასცდება, და ყოველ ჯერზე ვექტორი ყველაფერს აკოპირებს, რაც აქვს: 1, 2, 4, 8, … n-მდე. ეს ჯამი 2n-ზე ნაკლებია. დაამატე n ჩვეულებრივი ჩაწერა და n push ჯამში 3n-ზე ნაკლები ბიჯი გამოდის.

n ოპერაციაზე გადანაწილებით ეს თითოზე მაქსიმუმ 3 ბიჯია: ამორტიზებული O(1). ძვირი კოპირებები იმდენად იშვიათია, რომ საშუალოში იკარგება.

ეს მხოლოდ იმიტომ მუშაობს, რომ ტევადობა მრავლდება. ვექტორი ყოველ ჯერზე ფიქსირებული +10 უჯრით რომ იზრდებოდეს, ის 10, 20, 30, … ელემენტს დააკოპირებდა, ჯამში დაახლოებით n²/20-ს, და თითო push საშუალოდ O(n) იქნებოდა.

ნარინჯისფერი პიკები კოპირებებია 2, 3, 5, 9 და 17-ე push-ზე.

ფასი ერთი შეხედვით

წვდომა a[i]O(1)

push_backO(1) amortized

შუაში ჩასმა / წაშლაO(n)

ძებნა (დაულაგებელი)O(n)

დაიმახსოვრე

უწყვეტი მეხსიერება ინდექსაციას არითმეტიკად აქცევს, ამიტომ a[i] არის O(1).
შუაში ჩასმა ან წაშლა დანარჩენ მასივს ანაცვლებს და O(n) ღირს.
ტევადობის გაორმაგებით n push_back 3n ბიჯზე ნაკლები ჯდება: თითო ამორტიზებული O(1).

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: დათვალე წანაცვლების ბიჯები ჩასმისას: სცადე შენი მასივი და ჩასვი 0 ინდექსზე, მერე ბოლოში.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

მასივი მეხსიერებაში (ელემენტი = 4 ბაიტი)

0x10012[0]0x1045[1]0x1088[2]0x10c23[3]0x1109[4]0x11416[5]

მასივი ერთი მთლიანი ბლოკია. ის იწყება საბაზისო მისამართით 0x100, თითო ელემენტი 4 ბაიტს იკავებს.

ფსევდოკოდი

 1 array elements sit in contiguous memory 2 a[i]  →  address = base + i * elementSize   // O(1) 3 insert(i, x): shift a[i..] right by one      // O(n) 4   then write a[i] = x 5 push_back(x): append; vector doubles capacity when full

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

int მასივი 1000 მისამართიდან იწყება (4-ბაიტიანი int). რა არის a[25]-ის მისამართი?

№2

n ელემენტიან სიას აგებ ისე, რომ ყოველ ახალ ელემენტს ვექტორის თავში სვამ. რა არის ჯამური ღირებულება?

№3

რატომ ამრავლებს ვექტორი ტევადობას და არ უმატებს ფიქსირებულ რაოდენობას?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeConcatenation of Array დამწყები↗CSESIncreasing Array დამწყები↗LeetCodeRemove Element დამწყები↗LeetCodeMove Zeroes დამწყები↗LeetCodeRotate Array საშუალო↗