Kirish

Bajarilish vaqti

Algoritmlarni to‘liq tushunish uchun algoritm o‘z ishini bajarishi uchun zarur bo‘lgan vaqtni, ya’ni bajarilish vaqtini qanday baholashni tushunishimiz kerak.

Algoritmlarning bajarilish vaqtini o‘rganish muhim, chunki samarasiz algoritmdan foydalanish dasturimizni sekin yoki hatto ishlamaydigan qilib qo‘yishi mumkin.

Algoritmning bajarilish vaqtini tushunib, ehtiyojimizga mos algoritmni tanlay olamiz, dasturlarimizni tezroq ishlaydigan va katta hajmdagi ma’lumotlarni samarali qayta ishlaydigan qila olamiz.

Haqiqiy bajarilish vaqti

Turli algoritmlarning bajarilish vaqtini ko‘rib chiqayotganda, amalga oshirilgan algoritm ishlashi uchun sarflaydigan haqiqiy vaqtga qaramaymiz — sababi quyidagicha.

Agar algoritmni biror dasturlash tilida amalga oshirib, shu dasturni ishga tushirsak, u sarflaydigan haqiqiy vaqt ko‘plab omillarga bog‘liq bo‘ladi:

• algoritmni amalga oshirishda foydalanilgan dasturlash tili
• dasturchi algoritm uchun dasturni qanday yozgani
• amalga oshirilgan algoritmni ishga tushirish uchun foydalaniladigan kompilyator yoki interpretator
• algoritm ishlayotgan kompyuterning apparat ta’minoti
• operatsion tizim va kompyuterda bajarilayotgan boshqa vazifalar
• algoritm ishlov berayotgan ma’lumotlar hajmi

Algoritmning haqiqiy bajarilish vaqtiga shuncha turli omillar ta’sir qilar ekan, bir algoritm boshqasidan tezroq ekanini qanday bilishimiz mumkin? Bizga bajarilish vaqtining yaxshiroq o‘lchovini topish kerak.

Vaqt murakkabligi

Turli algoritmlarni baholash va solishtirish uchun algoritmning haqiqiy bajarilish vaqtiga qarash o‘rniga vaqt murakkabligi deb ataladigan tushunchadan foydalanish mantiqliroq.

Vaqt murakkabligi haqiqiy bajarilish vaqtiga qaraganda abstraktroq bo‘lib, dasturlash tili yoki apparat ta’minoti kabi omillarni hisobga olmaydi.

Vaqt murakkabligi — algoritmni katta hajmdagi ma’lumotlar ustida bajarish uchun zarur bo‘lgan amallar soni. Amallar sonini vaqt deb hisoblash mumkin, chunki kompyuter har bir amal uchun ma’lum vaqt sarflaydi.

Masalan, massivdagi eng kichik qiymatni topuvchi algoritmda massivdagi har bir qiymat bir martadan taqqoslanishi kerak. Har bir bunday taqqoslashni bitta amal deb hisoblash mumkin va har bir amal ma’lum vaqt oladi. Demak, algoritmga eng kichik qiymatni topish uchun kerak bo‘ladigan umumiy vaqt massivdagi qiymatlar soniga bog‘liq.

Shu sababli eng kichik qiymatni topish uchun ketadigan vaqt qiymatlar soniga chiziqli bog‘liq. 100 ta qiymat 100 ta taqqoslashni, 5000 ta qiymat esa 5000 ta taqqoslashni talab qiladi.

Vaqt va massivdagi qiymatlar soni orasidagi bog‘liqlik chiziqli bo‘lib, uni quyidagicha grafikda ko‘rsatish mumkin:

"Bitta amal"

Bu yerda "amallar" haqida gapirganda, "bitta amal" bir yoki bir nechta protsessor (CPU) siklini olishi mumkin; bu aslida vaqt murakkabligi nima ekanini tushunishimiz va turli algoritmlarning vaqt murakkabligini topishimiz uchun abstraksiyaga yordam beradigan so‘z, xolos.

Algoritmdagi bitta amalni algoritmning har bir iteratsiyasida yoki har bir ma’lumot bo‘lagi uchun bajariladigan, o‘zgarmas vaqt oladigan ish deb tushunish mumkin.

Masalan: Bubble sort algoritmi qilganidek, ikkita massiv elementini taqqoslash va biri ikkinchisidan katta bo‘lsa, ularning o‘rnini almashtirishni bitta amal deb tushunish mumkin. Buni bitta, ikkita yoki uchta amal deb tushunish aslida Bubble sort vaqt murakkabligiga ta’sir qilmaydi, chunki u o‘zgarmas vaqt oladi.

Agar amal algoritm qayta ishlayotgan ma’lumotlar hajmidan (\(n\)) qat’i nazar bir xil vaqt olsa, u "o‘zgarmas vaqt" oladi, deymiz. Ikki muayyan massiv elementini taqqoslash va biri ikkinchisidan katta bo‘lsa, ularning o‘rnini almashtirish massivda 10 ta yoki 1000 ta element bo‘lishidan qat’i nazar bir xil vaqt oladi.

Big O notatsiyasi

Matematikada Big O notatsiyasi funksiyaning yuqori chegarasini tavsiflash uchun ishlatiladi.

Informatikada esa Big O notatsiyasi, aniqroq aytganda, algoritmning eng yomon holatdagi vaqt murakkabligini topish uchun ishlatiladi.

Big O notatsiyasida qavsli bosh O harfi \(O() \) ishlatiladi, qavs ichida esa algoritmning bajarilish vaqtini ko‘rsatuvchi ifoda bo‘ladi. Bajarilish vaqti odatda \(n \) orqali ifodalanadi — bu algoritm ishlayotgan ma’lumotlar to‘plamidagi qiymatlar soni.

Quyida g‘oyani tushunib olish uchun turli algoritmlarga oid Big O notatsiyasining bir nechta misoli keltirilgan:

print( my_array[97] )

Turli algoritmlar uchun qiymatlar soni \(n\) oshganda vaqt qanday ortishi quyida ko‘rsatilgan:

Eng yaxshi, o‘rtacha va eng yomon holat

Big O notatsiyasini tushuntirishda "eng yomon holat"dagi vaqt murakkabligi haqida aytib o‘tildi, ammo algoritmda qanday qilib eng yomon holat bo‘lishi mumkin?

\(n\) ta qiymatli massivda eng kichik qiymatni topuvchi algoritm buning uchun \(n\) ta amal bajaradi va bu har doim bir xil. Demak, bu algoritmning eng yaxshi, o‘rtacha va eng yomon holatlari bir xil.

Ammo biz ko‘rib chiqadigan boshqa ko‘plab algoritmlarda qiymatlar soni \(n\) ni o‘zgarmas saqlasak ham, bajarilish vaqti qiymatlarning o‘ziga qarab ancha o‘zgarishi mumkin.

Barcha tafsilotlarga kirmasdan ham saralash algoritmining bajarilish vaqti u saralayotgan qiymatlarga qarab turlicha bo‘lishi mumkinligini tushunishimiz mumkin.

20 ta qiymatni qo‘lda eng kichigidan eng kattasigacha saralashingiz kerak, deb tasavvur qiling:

Buni tugatish uchun sizga bir necha soniya kerak bo‘ladi.

Endi deyarli saralangan 20 ta qiymatni saralashingiz kerak, deb tasavvur qiling:

Qiymatlarni juda tez saralay olasiz — shunchaki 20 ni ro‘yxat oxiriga ko‘chirasiz va ish tamom, shunday emasmi?

Algoritmlar ham xuddi shunday ishlaydi: bir xil hajmdagi ma’lumotlar uchun ular ba’zan sekin, ba’zan tez ishlashi mumkin. Shuning uchun turli algoritmlarning vaqt murakkabliklarini solishtira olish uchun odatda Big O notatsiyasi yordamida eng yomon holatga qaraymiz.

Big O’ning matematik tushuntirilishi

Matematika bo‘yicha tayyorgarligingizga qarab, bu bo‘limni tushunish qiyin bo‘lishi mumkin. U Big O’ni chuqurroq tushuntirib berishga ehtiyoj sezganlar uchun mustahkamroq matematik asos yaratishga mo‘ljallangan.

Agar buni hozir tushunmasangiz, xavotir olmang, keyinroq qaytishingiz mumkin. Agar bu yerdagi matematika siz uchun juda murakkab bo‘lsa, bu haqda ortiqcha qayg‘urmang — baribir ushbu darslikdagi turli algoritmlardan zavq olishingiz, ularni dasturlashni o‘rganishingiz va ular qanchalik tez yoki sekin ekanini tushunishingiz mumkin.

Matematikada Big O notatsiyasi funksiya uchun yuqori chegara hosil qilishda, informatikada esa ma’lumotlar qiymatlari soni \(n\) oshganda algoritmning bajarilish vaqti qanday ortishini tavsiflashda ishlatiladi.

Masalan, quyidagi funksiyani ko‘rib chiqing:

\[f(n) = 0.5n^3 -0.75n^2+1 \]

\(f\) funksiyasining grafigi quyidagicha ko‘rinadi:

Boshqa funksiyani ko‘rib chiqing:

\[g(n) = n^3 \]

Uni quyidagicha chizishimiz mumkin:

Big O notatsiyasidan foydalanib, \(O(g(n))\) \(f(n)\) uchun yuqori chegara, deyishimiz mumkin, chunki \(n\) yetarlicha katta bo‘lganda \(C \cdot g(n)>f(n)\) bo‘ladigan \(C\) konstantani tanlay olamiz.

Xo‘p, sinab ko‘raylik. \(C \cdot g(n) = 0.75 \cdot n^3\) bo‘lishi uchun \(C=0.75\) ni tanlaymiz.

Endi \(0.75 \cdot g(n)\) va \(f(n)\) ni bitta grafikda chizamiz:

Ko‘rib turibmizki, \(O(g(n))=O(n^3)\) \(f(n)\) uchun yuqori chegara, chunki 1 dan katta barcha \(n\) lar uchun \(0.75 \cdot g(n) > f(n)\).

Yuqoridagi misolda \(O(n^3)\) yuqori chegara bo‘lishi uchun \(n\) 1 dan katta bo‘lishi kerak. Bu chegarani \(n_0\) deb ataymiz.

Algoritmning vaqt murakkabligini baholashda \(O()\) faqat qiymatlar soni \(n\) katta bo‘lganda to‘g‘ri bo‘lishi normal holat, chunki vaqt murakkabligi aynan shunda muhim ahamiyat kasb etadi. Boshqacha aytganda: agar 10, 20 yoki 100 ta qiymatni saralayotgan bo‘lsak, algoritmning vaqt murakkabligi unchalik qiziq emas, chunki kompyuter baribir qiymatlarni qisqa vaqtda saralab beradi.