მასივი არის მეხსიერების თანმიმდევრული ბლოკი, რომელიც შეიცავს ერთი ტიპის ელემენტებს, დინდექსირებული 0-დან. რადგან ელემენტები ერთმანეთის გვერდით მდებარეობენ, i ელემენტის მისამართი გამოითვლება პირდაპირ base + i * elementSize ფორმულით, რაც იძლევა O(1) შემთხვევით წვდომას.
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| ოპერაცია | დრო |
|---|---|
| წვდომა ინდექსით | O(1) |
| ძებნა (დაუხარისხებელი) | O(n) |
| დამატება (დინამიური) | O(1) საშუო ხარჯით |
| ჩასმა/წაშლა დასაწყისში/შუაში | O(n) |
მასივები არის ფუძე უმეტეს სხვა სტრუქტურების ქვეშ — სტრიქონები, ჰეშ-ცხრილები, გროვები და დინამიური სიები ყველა აშენებულია მათზე.
მათი კეშის ლოკალურობა ხშირად იწვევს იმას, რომ "ნელი" Big-O მასივი სცემს "უფრო სწრაფ" მაჩვენებელზე დაფუძნებულ სტრუქტურას რეალურ ბენჩმარკებში.