Big O notatsiyasi: vaqt va xotira murakkabligi

Big O nimani anglatadi

Big O kirish ma’lumotlari hajmi n oshganda algoritm bajaradigan ish qanday o‘sishini tavsiflaydi. U soniyalarni o‘lchamaydi. U shunday savolga javob beradi: «Ma’lumotlar o‘n barobar ko‘paysa, bu kod qanchalik sekinlashadi yoki ko‘proq xotira talab qiladi?»

Ikki qoida uni sodda qiladi:

• Konstantalar tashlab yuboriladi: 2n ham, n + 100 ham O(n).
• Faqat eng tez o‘sadigan had muhim: n^2 + n — bu O(n^2).

Odatda Big O eng yomon holat uchun ko‘rsatiladi. Vaqt murakkabligi amallarni, xotira murakkabligi qo‘shimcha xotirani hisoblaydi.

Eng ko‘p uchraydigan beshta murakkablik

O(1): konstanta

Ish n ga bog‘liq emas.

def first(items):
    return items[0]

prices = {"apple": 3}
prices["apple"]  # lug‘atdan qidirish o‘rtacha O(1)

O(log n): logarifmik

Har bir qadam qolgan ma’lumotlarni ikkiga bo‘ladi. Odatiy misol — saralangan ro‘yxatda binar qidiruv.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

O(n): chiziqli

Ma’lumotlardan bir marta o‘tish.

def total(items):
    s = 0
    for x in items:
        s += x
    return s

O(n log n): chiziqli-logarifmik

Samarali universal saralashning narxi, masalan birlashtirib saralash yoki ko‘plab tillardagi o‘rnatilgan sorted().

O(n^2): kvadratik

Xuddi shu ma’lumotlar bo‘yicha sikl ichidagi sikl.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Ular qanchalik tez o‘sadi

Turli kirish hajmlari uchun amallarning taxminiy soni:

O‘nta elementda hammasi tez. Million elementda kvadratik kod trillion qadam bajaradi — bu darhol javob bilan hech qachon tugamaydigan so‘rov orasidagi farq.

O‘z funksiyangizni qanday baholash mumkin

1. n ni aniqlang: nima o‘sadi? Foydalanuvchilar, qatorlar, belgilar soni.
2. Oddiy amallar — O(1).
3. n bo‘yicha sikl tanani n ga ko‘paytiradi.
4. Ichma-ich sikllar ko‘paytiriladi: n bo‘yicha ikkita ichma-ich sikl O(n^2) beradi.
5. Ketma-ket bloklar qo‘shiladi va eng kattasi qoladi: O(n) + O(n^2) = O(n^2).
6. Har qadamda ikkiga bo‘lish O(log n) beradi.
7. Yashirin narxni tekshiring: x in list — O(n), x in set — o‘rtacha O(1); kesish va nusxalash — O(n).

Dublikatlarni tekshirishning klassik yaxshilanishi:

def has_duplicates(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Vaqt O(n^2) dan O(n) ga tushadi, lekin to‘plam sababli xotira O(1) dan O(n) ga oshadi. Bunday vaqtni xotiraga almashtirish amaliyotdagi eng ko‘p uchraydigan qarorlardan biri.

Ko‘p uchraydigan xatolar

• Sikl ichida O(n) kod chaqirilsa ham funksiyani O(n) deb hisoblash: bu O(n^2).
• Sikl ichida bazaga so‘rovlar: bitta o‘rniga N ta so‘rov ko‘pincha veb-ilovalarning haqiqiy zaif nuqtasi.
• Konstantalarni butunlay e’tiborsiz qoldirish: kichik n da kichik konstantali «yomonroq» algoritm tezroq bo‘lishi mumkin. Shubha bo‘lsa, o‘lchang.
• O‘nta element bilan ishlaydigan kodni optimallashtirish: Big O ma’lumotlar o‘sadigan joyda muhim.