Algortim murakkabligini baholash usullari Vaqt bo’yicha murakkabligini baholash

o’zgarmas ko’paytuvchini tashlab yuborish mumkin. Chunki bizga faqat baholashning o'zi kifoya, aniq hisob-kitob shart emas. Ya'ni:

• 
  kichik darajali ifoda kattaroq darajali ifodadan har doim sekinroq o'sadi
  

• 
  darajali ifoda har doim ekponensial ifodadan ko'ra sekinroq o'sadi. Ya'ni:
  

• 
  logarifmik ifoda darajali ifodadan ko'ra sekinroq o'sadi
  

• 
  sekinroq o’suvchi hadni tashlab yuborish mumkin. Ya'ni, algoritm murakkabligini hisoblashda hosil bo'lgan ifoda bir necha hadlardan iborat bo'lsa, ulardan faqat eng tez o'suvchisini olib qolishning o'zi yetadi: f + g = O(max(f, g))
  

Eng ko'p uchraydigan murakkabliklar va ularni taqqoslash

Endi esa dasturlash musobaqalaridagi algoritmik masalalarni yechishda eng ko'p uchraydigan assimptotikalarni ko'rib o'tamiz. Bunda ularni o'sish tartibida keltiramiz

Ularni taqqoslashni yanayam aniqroq tasavvur qilish uchun quyidagi grafikni keltiramiz

X: kiruvchi ma'lumot hajmi; Y: shu hajmdagi ma'lumot uchun bajariladigan amallar soni

Ko'rib turganingizdek bor yo'g'i n<10 bo'lgan holatda ham ularning farqi yaqqol ko'zga tashlanib turibdi. Bu farq ham n ortgani sari ortib boraveradi.

Keling endi agar tuzgan dasturimiz yuqoridagi algoritmik assimptotikalarni ishlatgan holatda masalani qancha vaqtda yechishini hisoblab ko'raylik. Bunda o'rtacha kompyuter sekundiga 10^9 ta amal bajaradi deb tasavvur qilsak:

Bu jadvalda hamma assimptotikalar ham keltirilmagan, buning o'rniga 1 sekundda maksimal 10^9 ta amal bajara oladigan O(n) etalon sifatida tanlangan.

Ko'p uchraydigan holatlar assimptotikalari:

Endi esa ba'zi holatlarning assimptotikalarini ko'rib chiqsak:

O(1) - masala yechimiga o'zgarmas vaqt sarflanadi va algoritm ishlash tezligi kiruvchi ma'lumotga bo'g'liq bo'lmaydi. Masalan, elementlari arifmetik progressiya hosil qiluvchi massiv summasini hisoblash

O(log(n)) - logarifmik algoritm har bir qadamda kiruvchi ma'lumot hajmini ma'lum qismlarga ajratib yuboradi (ko'pincha teng ikkiga bo'ladi).

O(n) - chiziqli algoritm har bir kiruvchi ma'lumotni bir martadan ko'rib chiqadi. Masalan, n ta elementdan maksimumini topishda. Odatda, eng optimal yechim shu assimptotikada ishlaydi, chunki doim har bir elementga hech bo'lmaganda bir marta murjaat qilish kerak bo'ladi.

O(n*log(n)) - bunday assimptotika, odatda, kiruvchi ma'lumotlarni saralash kerak bo'lgan paytda uchraydi. Chunki, samarali saralash algoritmlari shuncha amal bajaradi. Bundan tashqari har bir amal O(log(n)) ta amal bajarishni talab qiladigan ma'lumotlar tuzilmalari ham shu murakkablikda ishlaydi.

O(n^2) - kvadratik algoritmik ko'pincha yechimida ikkita ichma-ich sikl kelgan masalalarda uchraydi. Bunday vaqt bilan kiruvchi elementlar barcha juftliklarini ko'rib chiqish mumkin. (Masalan, Bubble sort)

O(n^3) - kubik algoritm. Kiruvchi elementlar barcha 3 lik juftliklarini ko'rib chiqish kerak bo'lganda ishlatilishi mumkin.

O(2^n) - bunday murakkablikdagi algoritm kiruvchi elementlarni (to'plamni) barcha qism to'plamlarini ko'rib chiqishda ishlatilishi mumkin. Masalan, {a, b, c} to'plam uchun (n = 3) barcha qism to'plamlar: bo'sh to'plam, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} va {1, 2, 3}, ya'ni 2^3 = 8 ta.

O(n!) - bunday algoritm kiruvchi to'plamni barcha permutatsiyalarini ko'rib chiqishda ishlatiladi. Misol uchun: {a, b, c} to'plam uchun (n = 3) barcha permutatsiyalar: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a), ya'ni 3! = 6 ta.

Kiruvchi ma'lumotlar hajmiga qarab to'g'ri yechim tanlash

Endi qaysi yechim taxminan qancha vaqt olishini va qanday yechim optimalroq bo'lishini bilib oldik. Darsimizning oxirida dasturlash musobaqalari masalalarida berilgan kiruvchi ma'lumotlar hajmiga qarab, vaqt limitidan o'tib ketmaslik uchun yechimingiz eng kamida qanday yechimda ishlashi kerakligini aniqlash haqida gaplashamiz.

Demak yana jadvalga murojaat qilamiz:



Ba'zi holatlarda boshlovchilar uchun masalalarda kiruvchi ma'lumotlar hajmi atayin kichik beriladi. Bunda eng oddiy yechimlardan ham, eng yaxshilaridan ham foydalanish mumkin.