Dinamik massiv

Oldingi qismda biz massivning muhim bir xususiyatini ko'rdik: klassik, qat'iy o'lchamli massiv yaratilganda uning kataklar soni bir marta belgilanadi va keyinchalik o'zgarmaydi. Bu tuzilma xotirada uzluksiz joy egallaydi va index orqali istalgan elementga O(1) vaqtda kirish imkonini beradi. Lekin bu qat'iylik ba'zan muammo tug'diradi.

Tasavvur qiling: siz serverga kelgan so'rovlarni ro'yxatga olmoqchisiz. Ular bir soatda 50 ta keladimi yoki 50 000 ta — oldindan bilmaysiz. Bayram kuni trafik o'n barobar oshishi mumkin. Agar 100 ta so'rovga joy ajratsangiz, 101-so'rov kelganida massiv to'lib qoladi. Agar 10 000 ta joy ajratsangiz, sokin kechalari xotiraning 99 foizi bekor turadi.

Dinamik massiv aynan shu muammoni hal qilish uchun yaratilgan: u tashqaridan o'lchami bemalol o'zgarayotgandek ko'rinadigan, lekin ichkarida klassik massiv bilan ishlaydigan ma'lumotlar tuzilmasi.

Daftar analogiyasi

Qo'lingizda 10 varaqlilk daftar bor. Darsga qatnashib, har kuni bir varaqdagi mavzular yozasiz. O'n kundan so'ng daftar to'ladi. Endi nima qilasiz? Yangi 20 varaqlilk daftar olasiz, eski yozuvlarni unga ko'chirasiz va yangi daftar bilan davom etasiz.

Dinamik massiv ham xuddi shunday ishlaydi. U ichida bir hajmli "daftar" — oddiy massiv — saqlaydi. Bu massiv to'lganda kattaroq yangi massiv ajratadi, eski elementlarni unga ko'chiradi va eski xotirani bo'shatadi. Tashqaridan qaraganda hech narsa o'zgargandek ko'rinmaydi — element qo'shaverasiz. Lekin ichkarida vaqti-vaqti bilan yashirin ko'chirish sodir bo'lib turadi.

Sig'im va uzunlik

Dinamik massivning ichki holatini tushunish uchun ikki tushunchani farqlash kerak:

uzunlik (length) — hozir nechta haqiqiy element saqlanayotgani;
sig'im (capacity) — qayta joy ajratmasdan nechta element joylasha olishi.

Sig'im:   8 ta katak
          +---+---+---+---+---+---+---+---+
Element:  | A | B | C | D |   |   |   |   |
          +---+---+---+---+---+---+---+---+
Uzunlik:  4 (haqiqiy elementlar)
Bo'sh:    4 (hali to'ldirilmagan)

Bu yerda uzunlik 4, sig'im esa 8. Yana to'rtta element qo'shish mumkin — xotirani qayta ajratish shart emas. Beshinchi element kelib qolgan zahira katakka yoziladi. Ammo to'qqizinchi element qo'shilmoqchi bo'lganda sig'im yetmaydi va kengaytirish boshlanadi.

Note

Dinamik massivning uzunligi foydalanuvchiga ko'rinadi. Sig'im esa ichki texnik detal — uni ko'pchilik tillar to'g'ridan-to'g'ri ko'rsatmaydi. Lekin u mavjud va xotira sarfiga bevosita ta'sir qiladi.

Kengaytirish qanday ishlaydi?

Sig'im to'lganda kengaytirish uch bosqichda bajariladi:

Yangi, kattaroq massiv uchun xotira ajratiladi.
Eski massivdagi barcha elementlar yangi massivga ko'chiriladi.
Eski massivning xotirasi bo'shatiladi.

Sig'im to'ldi:
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+

Yangi massiv (ikki barobar katta):
+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 |   |   |   |   |
+---+---+---+---+---+---+---+---+

Endi 5 qo'shiiladi:
+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |   |   |   |
+---+---+---+---+---+---+---+---+

Ko'chirish jarayonida barcha eski elementlar yangi joyga ko'chadi. Agar massivda n ta element bo'lsa, ko'chirish O(n) vaqt oladi. Bu qimmat amal. Lekin u kamdan-kam sodir bo'ladi — va aynan shu narsa dinamik massivni amalda samarali qiladi.

Nima uchun ikki barobar kengaytirish?

Ko'pgina implementatsiyalarda sig'im to'lganda yangi sig'im ikki baravar oshiriladi. Bu tasodifiy raqam emas.

Tasavvur qiling, siz ketma-ket element qo'shib borasiz:

1-element:  sig'im 1,  joy yetarli
2-element:  sig'im to'ldi → yangi sig'im 2,  1 ta element ko'chirildi
3-element:  sig'im to'ldi → yangi sig'im 4,  2 ta element ko'chirildi
5-element:  sig'im to'ldi → yangi sig'im 8,  4 ta element ko'chirildi
9-element:  sig'im to'ldi → yangi sig'im 16, 8 ta element ko'chirildi
17-element: sig'im to'ldi → yangi sig'im 32, 16 ta element ko'chirildi

n ta element qo'shish uchun jami qancha ko'chirish bajariladi?

1 + 2 + 4 + 8 + ... + n/2 ≈ 2n

Bu geometrik progressiya. Yig'indi ndan ikki baravar katta. Demak, n ta element qo'shish uchun jami ko'chirish soni 2n dan oshmaydi. Bu esa bitta element qo'shishning o'rtacha narxi O(1) ekanligini anglatadi.

Agar ikki baravar emas, bir barobar oshirilsa nima bo'ladi? Ya'ni sig'im har safar +1 oshirilsa:

1-element:  sig'im 1
2-element:  sig'im to'ldi → sig'im 2,  1 ko'chirish
3-element:  sig'im to'ldi → sig'im 3,  2 ko'chirish
4-element:  sig'im to'ldi → sig'im 4,  3 ko'chirish
...
n-element:  sig'im to'ldi → sig'im n,  n-1 ko'chirish

Jami ko'chirish: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 ≈ O(n²). Bu juda qimmat. Ikki baravar kengaytirish ko'chirishlarni geometrik progressiya orqali O(n) ga tushiradi.

Amortized O(1) — narxni taqsimlash

"Sig'im to'lganda ko'chirish O(n) bo'ladi, unda oxiriga qo'shish qanday O(1) bo'lishi mumkin?" — bu savol mantiqan to'g'ri.

Amortized tahlilda bitta amalni individual emas, ko'p amalning o'rtacha narxini hisoblaymiz. Bu g'oyani moliyaviy o'xshashlik orqali tushuntirsak:

Har bir element qo'shishda "3 ta kredit" to'laysiz deb faraz qiling: - 1 kredit — hozirgi qo'shish uchun; - 2 kredit — kelajakdagi ko'chirish uchun zahirada saqlanadi.

Sig'im to'lib, 8 ta element ko'chirilishi kerak bo'lsa, ular allaqachon "zahirada" 2 × 8 = 16 kredit to'plagan. Ko'chirish uchun 8 kredit yetadi, qolgan 8 ta kredit yana shu yangi massivda biriktiriladi.

Bu "bank hisobi" tushunchasi amortized tahlilning asosi. Real vaqt har xil bo'ladi — ba'zi qo'shishlar O(1), ba'zilari O(n). Lekin n ta qo'shish uchun jami sarflangan ish O(n), shu sababli bitta qo'shishning amortized narxi O(1).

Warning

"Amortized O(1)" va "kafolatlangan O(1)" bir xil emas. Har safar qo'shish bir xil vaqtda bajariladi degani emas. Kengaytirish bo'ladigan qo'shish sekinroq bo'ladi. Agar tizim har bir amalni aynan bir xil vaqtda bajarishini talab qilsa (masalan, real vaqtli tizimlar), dinamik massivning kengaytirish jarayoni muammo tug'dirishi mumkin.

Asosiy amallarning murakkabligi

Amal	Vaqt murakkabligi	Izoh
Oxiriga qo'shish	Amortized `O(1)`	Sig'im yetarli bo'lsa `O(1)`, to'lib ketsa `O(n)` ko'chirish
Index orqali o'qish	`O(1)`	Klassik massiv kabi manzil hisoblanadi
Index orqali o'zgartirish	`O(1)`	Faqat bitta katakning qiymati o'zgaradi
Boshiga yoki o'rtasiga qo'shish	`O(n)`	Keyingi elementlar o'ngga suriladi
Oxiridan o'chirish	`O(1)`	Boshqa elementlar siljitilmaydi
Boshidan yoki o'rtasidan o'chirish	`O(n)`	Keyingi elementlar chapga suriladi
Qidirish (linear)	`O(n)`	Har bir element tekshirilishi mumkin
Uzunlik	`O(1)`	Uzunlik alohida o'zgaruvchida saqlanadi

Kengaytirish strategiyalari

Ko'pgina implementatsiyalar sig'imni ikki barobar oshiradi, lekin bu yagona yondashuv emas:

ikki baravar (×2): Java ArrayList, Go slice kabi tuzilmalarda keng tarqalgan;
1.5 baravar (×1.5): xotira sarfini biroz kamaytirishga harakat qilib, amortized samaradorlikni saqlab qoladi;
belgilangan miqdor (masalan, +64): kichik massivlar uchun mos, katta massivlarda samarasiz.

Qaysi koeffitsient tanlanishi xotira va tezlik o'rtasidagi muvozanatga bog'liq. Ko'pchilik amaliy holatlarda ikki baravar kengaytirish yaxshi muvozanat beradi.

Xotiradagi haqiqiy holat

Kengaytirish vaqtida yangi massiv xotirada boshqa joyda joylashishi mumkin:

Eski massiv:           Yangi massiv:
Manzil: 1000-1031      Manzil: 5000-5063

+--+--+--+--+--+--+--+--+         +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10|20|30|40|50|60|70|80|    →    |10|20|30|40|50|60|70|80|  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+         +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Eski manzil (1000) endi ishlatilmaydi. Tizim bu xotirani boshqa maqsadlar uchun qaytarib oladi. Yangi massiv (5000) boshqa joyda joylashgan bo'lsa-da, foydalanuvchi uchun hech narsa o'zgarmaydi — element qo'shishda davom etaveradi.

Bu klassik massivdan muhim farq. Klassik massiv har doim bir xil xotira manzilida turadi. Dinamik massivning manzili kengaytirish vaqtida o'zgarishi mumkin. Shu sababli ba'zi past darajali tillarda massiv kengaytirilgandan keyin eski manzilga bo'lgan ko'rsatkichlar yaroqsiz bo'lib qolishi mumkin.

Dinamik massiv qayerda ishlatiladi?

Dinamik massiv dasturlashning ko'plab joylarida yashirincha ishlaydi:

Brauzerning ochiq yorliqlari. Siz yangi yorliq ochasiz, u ro'yxatga qo'shiladi. Yorliqlar soni oldindan noma'lum — brauzer dinamik massivga o'xshash tuzilmadan foydalanadi.
Matn muharriri. Foydalanuvchi harflarni birma-bir kiritadi. Har bir harfni alohida o'zgaruvchida saqlab bo'lmaydi. Matn ichki dinamik struktura yordamida saqlanadi va o'sib boradi.
Qidiruv natijalari. Qidiruv tizimi nechta natija topilishini oldindan bilmaydi. Topilgan natijalar dinamik tuzilmada yig'iladi va foydalanuvchiga qaytariladi.
Server jurnallari. Serverga kelgan so'rovlar ro'yxati vaqt o'tishi bilan ortib boradi. Bu ro'yxatni dinamik massiv sifatida tasavvur qilish mumkin.
O'yin ob'ektlari. O'yinda yangi raqiblar, o'qlar va portlashlar paydo bo'lib yo'qolib turadi. Ularning ro'yxati dinamik ravishda o'zgaradi.

Afzalliklari

Dinamik massiv klassik massivning asosiy afzalliklarini saqlab qoladi va ustiga qo'shimcha moslashuvchanlik qo'shadi:

Index orqali elementga kirish O(1) bo'lib qoladi.
Oxiriga element qo'shish amortized O(1) — ya'ni ko'pincha tez, kamdan-kam hollarda sekinroq.
Elementlar soni oldindan noma'lum bo'lganda qulay.
Kengaytirish foydalanuvchidan yashiringan — faqat element qo'shasiz, qolgan ish avtomatik bajariladi.

Cheklovlari

O'rta va boshiga qo'shish va o'chirish O(n) bo'lib qoladi.
Kengaytirish paytida O(n) vaqt sarflanadi — bu ba'zan kutilmagan kechikish tug'dirishi mumkin.
Sig'im hamma vaqt to'liq band bo'lmaydi — ortiqcha xotira zahirada turadi. Sig'im 8 bo'lib, uzunlik 5 bo'lsa, 3 ta katak bekor turadi.
Katta massivlar uchun kengaytirish eski va yangi massivni bir vaqtda xotirada saqlashni talab qiladi. Kengaytirish paytida qisqa muddatda xotira sarfi ikki baravar bo'lishi mumkin.

Dinamik massivni qachon ishlatmaslik kerak?

Dinamik massiv universallik jihatidan qulay, lekin har doim optimal tanlov emas:

O'rta va boshiga ko'p qo'shish kerak bo'lsa. Har bir bunday amal O(n) bo'lgani uchun bog'liq ro'yxat (linked list) yaxshiroq bo'lishi mumkin.
Element qo'shish vaqtini kafolatlash zarur bo'lsa. Amortized O(1) o'rtacha bo'lsa-da, kengaytirish paytida sekinlashish bo'ladi. Real vaqtli tizimlar bundan aziyat chekishi mumkin.
Ma'lumot hajmi aniq va o'zgarmas bo'lsa. Avvaldan o'lchamni bilsangiz, fixed-size massiv ortiqcha kengaytirish va nusxa ko'chirish xarajatisiz aniqroq ishlaydi.
Xotira o'ta cheklangan bo'lsa. Dinamik massivning zahira sig'imi xotirani vaqti-vaqti bilan bekor tutib qoladi.

Dinamik massiv va fixed-size massiv qachon tanlanadi?

Savol	Fixed-size massiv	Dinamik massiv
Elementlar soni oldindan ma'lummi?	Ha	Noma'lum yoki o'zgaruvchan
Boshiga/o'rtasiga ko'p qo'shish bormi?	Ikkalasi ham mos emas	Ikkalasi ham mos emas
Oxiriga ko'p qo'shish bormi?	Faqat joy bo'lsa	Ideal
Xotira sarfi aniq bo'lishi kerakmi?	Ha	Yo'q (zahira bo'ladi)
Kengaytirish kechikishi muammo bo'ladimi?	Yo'q (kengaymaydi)	Ha, hisobga olinishi kerak

Eng muhim xulosa

Dinamik massiv — klassik massiv ustiga qurilgan qatlam. U kengayish mantiqini sizdan yashiradi va "o'zi o'sib boradigan" kolleksiya tassurotini beradi. Lekin ichkarida u hali ham oddiy massiv, manzil hisoblash va uzluksiz xotira ustiga qurilgan.

Uni ishlatganda uchta narsani yodda tutish kerak:

Oxiriga qo'shish amortized O(1), lekin har doim kafolatli O(1) emas.
O'rta va boshiga qo'shish yoki o'chirish — klassik massiv kabi O(n).
Sig'im va uzunlik farqi xotira sarfini tushunishda muhim.

Keyingi qismda massivda qidirish mavzusini ko'ramiz: saralanmagan massivda qanday qidiriladi va massiv saralangan bo'lsa qidiruvni qanday tezlashtirish mumkin.

📍 Toshkent, O'zbekiston
🗓️ 4-Avgust, 2026-yil
👤 Farrux Elomonov