DSA massivlar
Massivlar
Massiv — bir nechta elementni saqlash uchun ishlatiladigan ma’lumotlar tuzilmasi.
Massivlardan ko‘plab algoritmlar foydalanadi.
Masalan, quyidagi animatsiyada ko‘rsatilganidek, massivni ko‘rib chiqib, eng kichik qiymatni topish uchun algoritmdan foydalanish mumkin:
Tezlik:
{{ msgDone }}Eng kichik qiymat: {{ minVal }}
Python’da massivni quyidagicha yaratish mumkin:
my_array = [7, 12, 9, 4, 11]Eslatma: Yuqoridagi Python kodi aslida Python’ning "list" ma’lumot tipini hosil qiladi, ammo ushbu darslik doirasida "list" ma’lumot tipidan massiv kabi foydalanish mumkin. Python ro‘yxatlari (list) haqida bu yerda batafsil bilib oling.
Massivlar indekslangan, ya’ni massivdagi har bir element indeksga — element massivning qayerida joylashganini bildiruvchi songa ega. Ushbu darslikdagi dasturlash tillari (Python, Java va C) massivlar uchun noldan boshlanadigan indekslashdan foydalanadi, ya’ni massivdagi birinchi elementga 0 indeksi orqali murojaat qilish mumkin.
Python’da ushbu kod massivning birinchi elementini (7 qiymatini) konsolga chiqarish uchun 0 indeksidan foydalanadi:
Algoritm: massivdagi eng kichik qiymatni topish
Massiv ma’lumotlar tuzilmasidan foydalanib, birinchi algoritmimizni yaratamiz.
Quyida massivdagi eng kichik sonni topish algoritmi keltirilgan.
Qanday ishlaydi:
- Massivdagi qiymatlarni birma-bir ko‘rib chiqing.
- Joriy qiymat shu paytgacha uchraganlar ichida eng kichigi ekanini tekshiring va agar shunday bo‘lsa, uni saqlab qo‘ying.
- Barcha qiymatlar ko‘rib chiqilgach, saqlangan qiymat massivdagi barcha qiymatlarning eng kichigi bo‘ladi.
Eng kichik qiymatni topish algoritmi qanday ishlashini ko‘rish uchun quyidagi simulyatsiyani sinab ko‘ring (animatsiya ushbu sahifaning yuqorisidagi bilan bir xil):
Tezlik:
{{ msgDone }}Eng kichik qiymat: {{ minVal }}
Navbatdagi simulyatsiya ham xuddi yuqoridagi simulyatsiya kabi massivdagi eng kichik qiymatni topadi, ammo bu yerda eng kichik qiymatni topish uchun massiv ichidagi sonlar qanday tekshirilishini ko‘rishimiz mumkin:
Amalga oshirish
Algoritmni haqiqiy dasturlash tilida amalga oshirishdan oldin, odatda, avval uni bosqichma-bosqich jarayon sifatida yozib olish oqilona bo‘ladi.
Agar algoritmni inson tili va dasturlash tili o‘rtasidagi biror ko‘rinishda yozib olsangiz, keyinchalik uni amalga oshirish osonroq bo‘ladi, chunki dasturlash tili sintaksisining barcha tafsilotlariga g‘arq bo‘lib qolishdan saqlanamiz.
- "minVal" o‘zgaruvchisini yarating va uni massivning birinchi qiymatiga tenglashtiring.
- Massivdagi har bir elementni ko‘rib chiqing.
- Agar joriy elementning qiymati "minVal" dan kichik bo‘lsa, "minVal" ni shu qiymatga yangilang.
- Massivdagi barcha elementlar ko‘rib chiqilgach, "minVal" o‘zgaruvchisida eng kichik qiymat saqlanadi.
Xohlasangiz, algoritmni dasturlash tiliga ko‘proq o‘xshaydigan tarzda ham yozishingiz mumkin, masalan:
Variable 'minVal' = array[0]
For each element in the array
If current element < minVal
minVal = current element
Eslatma: Yuqorida yozgan algoritmning ikkala bosqichma-bosqich tavsifini "psevdokod" deb atash mumkin. Psevdokod — dastur nima qilishining inson tili va dasturlash tili o‘rtasidagi tilda yozilgan tavsifi.
Algoritmni yozib olganimizdan so‘ng, uni muayyan dasturlash tilida amalga oshirish ancha osonlashadi:
Misol
Python:
my_array = [7, 12, 9, 4, 11]
minVal = my_array[0] # Step 1
for i in my_array: # Step 2
if i < minVal: # Step 3
minVal = i
print('Lowest value: ',minVal) # Step 4Algoritmning vaqt murakkabligi
Algoritmlarni o‘rganishda ko‘pincha algoritm bajarilishi uchun ma’lumotlar to‘plami hajmiga nisbatan qancha vaqt ketishini ko‘rib chiqamiz.
Yuqoridagi misolda algoritm bajarilishi uchun zarur vaqt ma’lumotlar to‘plami hajmiga proporsional, ya’ni chiziqli bog‘liq. Buning sababi, eng kichik qiymatni topish uchun algoritm massivning har bir elementiga bir martadan murojaat qilishi kerak. Massivda 5 ta qiymat bo‘lgani uchun sikl 5 marta bajarilishi kerak. Agar massivda 1000 ta qiymat bo‘lganida, sikl 1000 marta bajarilishi kerak bo‘lardi.
Eng kichik qiymatni topish uchun zarur bo‘lgan taqqoslash amallari soni va massiv hajmi o‘rtasidagi bu bog‘liqlikni ko‘rish uchun quyidagi simulyatsiyani sinab ko‘ring.
Vaqt murakkabligi nima ekanligi haqida batafsilroq tushuntirish uchun ushbu sahifaga qarang.
Ushbu darslikdagi har bir algoritm uning vaqt murakkabligi bilan birga taqdim etiladi.
{{ this.userX }}
Amallar: {{ operations }}
DSA mashqlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!