Big O

Big O - bu yozilgan algoritm qanchalik samaradorligini aniqlovchi o'lchov. Bu o'lchov algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki xotira qanday o'zgarishini taqribiy ko'rsatadi.

Big O - Algoritm tezligini baholash standarti.

• Birligi - Operatsiyalar soni
• Eng yomon holat uchun baholaydi

Big O notation vaqt va xotira murakkabligini eng maksimum qiymatini o'lchash uchun ishlatiladi. Uning vazifasi bizning Algoritm yoki ma'lumotlar struktuamiz eng yomon holat(worst-case)da qanday ishlashini tasvirlaydi.

Dasturlarni odatda worst-case holati o'lchanadi. Chunki bu orqali siz o'z dasturingiz eng yomon holatda qanday ko'rsatgichda ishlashini bilib olasiz. Bu huddi marafon yuguruvchisi kasal va yugurishga loyiq emas holatida qanday natija ko'rsatishini o'lchashdek gap. Demak biz Big O notation nima uchun xizmat qilishini qisman tushunib oldik.

O'lchovlar

Agar kiruvchi qiymat hajmi n bo'lsa, algoritm murakkabliklari quyidagicha ifodalanadi:

Tavsiflar

1. O(1) — Doimiy murakkablik
   Algoritmga kiruvchi qiymatlar (n) o'sib borsa ham, algoritm ishlashi uchun ketadigan vaqt yoki ishlatiladigan xotira miqdori o'zgarmaydi.

2. O(n) — Chiziqli murakkablik
   Kiruvchi qiymat hajmi (n) ortgani sari algoritm ishlash vaqti yoki xotira ham shu nisbatda ortadi.
   Masalan, agar algoritmda n ta elementdan iborat massiv yaratilsa, xotira murakkabligi O(n) bo'ladi.

3. O(log n) — Logarifmik murakkablik
   Kiruvchi qiymat hajmi ortgani sari algoritm ishlash vaqti yoki xotirasi juda sekin — logarifmik tezlikda o'sadi. Masalan, binary search algoritmi.

4. O(n²) — Kvadratik murakkablik
   Kiruvchi qiymat hajmi ortgani sari algoritm ishlash vaqti yoki xotirasi kiruvchi qiymatning kvadratiga proporsional ravishda ortadi. Odatda ichma-ich sikllarda uchraydi.

5. O(n log n) — Chiziqli-logarifmik murakkablik
   Bu murakkablik chiziqli va logarifmik o'sish kombinatsiyasidir va ko'pincha samarali saralash algoritmlarida (masalan, merge sort) uchraydi.

6. O(2^n) — Eksponentsial murakkablik
   Kiruvchi qiymat hajmi ortgani sari algoritm ishlash vaqti yoki xotirasi juda tez — eksponentsial tezlikda ortadi. Bunday algoritmlar katta n uchun amalda yaroqsiz bo'lib qoladi.

Big O qoidalari

O'zgarmaslarni tushirib qoldirish:

O(n + n) = O(2*n) - quyidagicha vaqt talab qiluvchi algoritm aslida O(n). Bu yerdagi 2 soni o'zgarmas, ya'ni algoritmga kiruvchi qiymat ortib boragni sari u o'zgarmaydi. Shuning uchun uni bemalol tushirib qoldirish mumkin.

Dominant bo'lmaganlarini tushirib qoldirish:

O(n^2 + n ^2) = O(2 * n^2) - bundan 2 ni, ya'ni bitta n^2 ni tushirib qoldirishimiz mumkin (o'zgarmaslarni tushirib qoldirish qoidasiga ko'ra). O(n^2 + n) - bu ifodadachi? Avvalgi ifodada bemalol bitta n^2 ni tushirib qoldirgan bo'lsak, bunisida n ni ham tushirib qoldirishimiz mumkin. Chunki, u algoritmga kiruvchi qiymat oshib borgani sari n^2 chalik oshmaydi, uning o'zgarishi deyarli sezilarsiz.

Misol

Keling linear search (chiziqli qidiruv) ni nol bosqichdan boshlab Big-O bilan qanday hisoblanishini ko'rib chiqamiz.

Massivda element qidiramiz:

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Linear search algoritmi massiv uzunligi n bo'lsa, eng yomon holatda barcha n ta element tekshiriladi. Har bir iteratsiyada bitta taqqoslash bajariladi (arr[i] == x), shuning uchun bajariladigan elementar amallar soni T(n) = n ga teng bo'ladi. Demak, vaqt chiziqli o'sadi va algoritmning asimptotik vaqt o'sishi O(n) ga teng bo'ladi.

Chiziqli qidiruvning vaqt bo'yicha o'zgarish grafigi:

[O(n) uchun]

T(n)
|
|          *
|       *
|    *
| *
+------------------> n

Agar O(1) bo'lsa grafik quyidagi ko'rinishda bo'ladi:

[O(1) uchun]

T(n)
|
|
|       
|    
|------------------- 
+------------------> n

• https://dev.to/udilbar/big-o-haqida-gaplashamiz-4ni9
• https://farruxnet.uz/blog/2024/02/05/big-o---nima
• https://42.uz/course/express-algoritm/algoritmlar-xotira-va-katta-o/katta-o
• https://github.com/spring1843/go-dsa/