Biz haqimizda
Biz oddiy bir O'zbek xalqini rivoji uchun kichik bir hissasini qo'shmoqchi bo'lgan yigit va qizlarmiz. Ushbu loyihadan maqsad barchaga sifatli va qiziqarli ilm ulashish.
O'ylaymizki biz bu ishni yaxshi uddalaymiz va sizlarga siz "qiyin" deb o'ylagan narsalarni qanchalik osonligini tushuntiramiz insha'Alloh.
Loyihani riovji uchun hissa qo'shayotganlarni haqiga duo qilib qo'ying. Agarda o'z hissangizni qo'shmoqchi bo'lsangiz bunisiga ham ko'naveramiz 😌
Moddiy hissa qo'shish uchun buy me a coffee linkini ustiga bosib ximmatingizni ko'rsating. Ma'naviy hissa qo'shish uchun github sahifamizga o'tib "contribute" (opens in a new tab) qo'llanmasini o'qib chiqing.
Computer Scienceda biz ko'pincha algoritmlarning ishlashini tahlil qilishga qiziqamiz. Algoritm ishlash tezligini aniqlash uchun turli xil inputlar uchun algoritmimiz qancha vaqt sarflayotganini bilishimiz kerak. Misol uchun ro'yxatni tartiblaydigan algoritm yaratsak, u 10 ta raqam uchun qancha vaqt, 100 ta raqam uchun qancha vaqt, 1000 ta raqam uchun qancha vaqt ketishini o'lchashimiz mumkin.
Qachonki gap Algoritm tahlili haqida ketganda, bizga quyidagi ikki narsa doim qiziq bo'lishi lozim:
- Time - Qancha vaqt ketkazayabdi? (Nechta operatsiya bajaradi)
- Memory - Qancha xotira ketkazayabdi? (Qancha joy oladi)
Bilamizki hayotda o'lchovchi asboblar mavjud, masalan suvni o'lchash uchun litr yozilgan maxsus konteynerlardan foydalanamiz, uzunlikni o'lchash uchun sm yoki m o'lchamlari bor lineyka va ruletkalardan foydalanamiz. Ammo Algoritmlar uchun nimadan foydalanamiz?
Big O notation - Katta O belgisi
Big O notation Algoritmlarni tezligini o'lchash uchun ishlatiladigan asbob deb olsak bo'ladi. Algoritmga qanchalik katta hajmdagi ma'lumot kiritilsa u o'sha ma'lumot ustida bajaradigan operatsiyalar soni ham oshib boradi. Aynan shu orqali biz bilishimiz mumkinki, qancha xajmdagi ma'lumot uchun bizning algoritmimiz qancha vaqt va xotira talab qilishini.
Big O notationni tushunish uchun Matematikaga biroz murojaat qilamiz. Chunki Dasturlashda Matematikani o'rni juda muhim!
Matematikada funkisya degan tushuncha mavjud. Biz uni mana bu ko'rinishda ifodalashimiz mumkin.
f(x) = x + 2
Bu yerda biz f(x) dagi xga necha qiymatni bersak u o'sha qiymatni qavsdan keyingi ifodaga ham beradi degani misol uchun mana bunday:
f(10) = 10 + 2
Dasturlashga buni qanday dahli bor deyishingiz mumkin ammo shoshilmang endi yetib kelayabmiz. xga qancha katta qiymat bersak shuncha katta qiymat olayabmiz. Endi tasavvur qiling qiyinroq funksiyalarda bu ko'rsatgichlar qanchalik kattarishini. Endi algoritmlarni qanday o'lchashlikga o'tsak bo'ladi.
Qachonki biz algoritmlarni tahlil qilganimizda, qancha kattalikdagi qiymatga nechta operatsiya bajarayabdi va qancha xotira talab qilayabdi degan savolni ilg'or suramiz.
Tasavvur qiling, bizni algoritm berilgan arraydagi qiymatlardan faqat juft sonlarni yangi arrayga qo'shib, oxirida o'sha arrayni qaytarishi kerak.
Yuqorida keltirilgan funksiyani oladigan bo'lsak biz qanchalik kattalikda array bersak u shunchalik ko'p operatsiya bajaradi. Misol uchun [1, 2, 3, 4, 5] ni bersak u 5ta sonni ham tekshiadi va ularni ichidan nechtasi juft bo'lsa uni yangi arrayga o'tkazadi. Agar array ichidagi elementlar soni 100ta bo'lsa 100ta operatsiya, n ta bo'lsa n ta operatsiya sodir qiladi.
Time Complexity - Vaqt murakkabligi
Biz buni O(n) ko'rinishda o'lchasak bo'ladi. Chunki qanchalik elementlar ko'p bo'lsa algoritm shunchalik ko'p operatsiya bajaradi. Ya'ni siz 100ta elementli array bersangiz funksiyadagi loop 100 marta iteratsiya qiladi, 1000 ta bersangiz 1000 marta iteratsiya qiladi. Har bir iteratsiya esa bu bitta operatisya (harakat) degani.
Big O notation - algoritmni worst case xolati uchun ishlatiladi. Ya'ni worst case - eng yomon xolati deb tarjima qilsak bo'ladi.
Biz bu tahlilga algoritmimiz eng yomon ko'rsatkichda ishlaganda n marta ishlaydi deb qarasak bo'ladi. Agarda sizning algoritmingiz O(n) ko'rsatgichda bo'lsa dasturlashda uni Linear Time deb atashadi. Endi esa keling xotiraga ham to'xtalib o'tsak qanday qilib xotirani o'lchashimiz mumkin?
Space Complexity
Biz xotira murakkabligini MB yoki GB larda o'lchamaymiz biz uni ham Big O notation orqali o'lchaymiz. Ammo qanday deyishingiz mumkin? Keling uni ham ko'rib chiqsak.
Yuqoridagi kodni Time Complexitysi O(n) bo'lgan bo'lsa Space Complexitysi ham O(n) bo'layabdi. Ammo nimaga asoslanib, keling tushuntiraman.
Bu yerda array hajmi oshgani sari biz qaytaradigan result nomli array hajmi ham oshib boradi. Agar biz 50ta juft sonlardan iborat array kiritsak u barcha elementlarni resultga qo'shishiga to'g'ri keladi chunki ularni 50tasi ham juft. Ya'ni aytib o'tganimdek Big O notation worst case holatini o'lchash uchun ishlatiladi.
Agar biz 100ta element bor array bersak va arraydagi 50ta raqam juft, 50tasi esa toq sonlardan iborat bo'lsa bining ko'rsatgich O(n/2) ko'rsatgichni beradi. Ammo foydalanuvchi qanday array berishi bizga noma'lumo bo'lgani uchun ham biz uni O(n) deb olaveramiz. Demak bu narsaga tushundingiz deb umid qilaman.
O'lchov birliklari juda ko'p. Ularni ba'zilarini hozir ushbu qo'llanma davomida o'rganishingiz mumkin, qolganlarini esa sayohatimiz va o'rganish paytida kashf qilib ketamiz.
Time Complexities
Constant Time - O(1)
Constant - o'zgarmas degan ma'noni anglatadi. Matematikada konstant qiymat nimada bor desa men pi ≈ 3.14159 ni ayta olaman. Biz constant qiymatni Big O da O(1) deb o'lchaymiz. Nima uchun aynan 1 soni keltirilganini tushuntirishga menimcha xojat yo'q chunki qiymat birxil qolishi aytilayabdi. Kelin endi misol bilan ko'rsak
Yuqorida keltirilgan kodda bizning access_element funksyamizga istalgan kattalikda input bermaylik u bu ishni qilishga bir xil vaqt sarflaydi. Ya'ni operatsiyalar soni bu yerda 1ta.
Bu ham huddi shunday istalgan xajmdagi qiymat bermaylik operatsiyalar soni oshmaydi ya'ni doim bitta operatsiya amalga oshiradi. Shuning uchun ham uni worst caseda O(1) deb o'lchaymiz.
Linear Time - O(n)
Linear - Chiziqli degan ma'noni anglatadi. Tasavvur qiling oldingizda 100ta xona bor va har bir xona eshigida uning raqami bor. Xonalarni 99tasi bo'sha ammo bittasida xazina yashiringan. Siz esa o'sha xazinani topishingiz kerak. Xonalarni siz 1-eshikdan ochishni boshlaysiz keyin 2-eshik keyin 3-eshik va h.k.z.
Eng ko'pi bilan siz 100ta xonani barchasini ochishingizga to'g'ri keladi. Ko'rib turibsizki omadingiz bo'lsa uni 1tada ham topishingiz mumkin. Agar unday bo'lmasa demak 100ta eshikni ham ochib ko'rasiz. Bir narsani yana eslatib o'taman biz Big O notation bilan faqat worst case holatini tahlil qilamiz. Kelin endi kod bilan ko'radigan bo'lsak.
Yuqoridagi kodda tasvirlanganidek biz result degan o'zgaruvchi ochib uni 0ga tenglashtirdik. Va keyin for loop orqali, funksiyaga beriladigan list qiymatini iteratsiya qilamiz. Iteratsiya har bir raqamni result o'zgaruvchisizga increment qilib borayabdi va oxirida esa uni qaytarayabdi.
Demak bu yerda operatsiyalar soni bevosita funksiyaga beriladigan listning hajmiga bog'liq. Agar listda 23 ta element bo'lsa funksiyamiz 23 operatsiya bajaradi, agar 1 ta bo'lsa 1ta agar nta bo'lsa nta. Biz buni O(n) deb o'lchadik!
Quadratic Time - O(n2)
Quadratic - Kvadrat darajali degan ma'noni anglatadi. Tasavvur qiling ishxonada ho'jayiningiz sizga "Xonani 2 marta tekshiring" desa siz 4 marta tekshirasiz, "4 marta tekshiring" desa siz 16 marta tekshirasiz. Mana shu jarayon aynan quadratic deb atasak bo'ladi.
Yuqorida keltirilgan kodda nested-loop tasvirlangan. Biz funksiyaga necha qiymatni bersak u o'sha qiymatni kvadratichalik ko'p operatsiya bajaradi. Agar biz unga 2 ni kiritsak u 4 ta operatsiya qiladi, agar 5 ni kiritsak u 25 ta operatsiya bajaradi. Demak biz uni O(n2)
Space Complexities
Constant Space
Yuqorida keltirilgan kodning space complexitysi O(1). Sababi bizning funksiyamiz 100 ta elementli listga ham 1 000 000 000 elementli listga ham bir xil ishlaydi. Operatsiyalar soni ko'p bo'lgani bilan biz barchasini faqat bitta result degan o'zgaruvchiga saqlayabmiz.
Mana bu kodda ham Space Complexity O(1)ga teng. Chunki bizda funksiya boshlanishida ham tugashida ham faqat 2ta o'zgaruvchi qolayabdi. Ya'ni funksiyamiz yangi o'zgaruvchilar ochmayabdi, faqat bor o'zgaruvchilarni qiymati o'zgarayabdi. Demak agar funksiyangizdagi o'zgaruvchilar soni oshmasa.
Linear Space
Bu funksiya berilgan list ichida takrorlangan elementlar sonini sanaydi. Keling pastda qiymat berib ko'ramiz va berilgan qiymatga u qanday javob berishini Output orqali ifodalaymiz.
Yuqorida ko'rib turganingizdek array ichida takrorlanmaydigan so'zlar bo'lsa worst caseda bizning funksiyamizni Space Complexitysi O(n) ni tashkil qiladi. Agar omadimiz kelib takrorlanuvchi so'zlar bo'lsa n ta emas 1 ta ham bo'lishi mumkin.
Quadratic Space
Yuqoridagi funksiya list ichidagi har bir elementni sherik qilib pairs degan yangi listga qo'shib boradi.
Ko'rib turibsizki listimiz hajmi qancha kattalashsa qaytariladigan qiymat soni ham uning kvadratiga teng bo'ladi. Yuqoridagi misolda bizning listimizda 3 ta element bor edi ammo funksiya qaytargan yangi list esa 9ta elementdan iborat bo'ldi. Shuning uchun ham biz uni O(n2) deb o'lchaymiz.
Yana bir necha misolla keltirishimiz mumkin ammo qolganini sayohatimiz davomida o'rganib ketamiz. Hozircha shular edi.