Algoritmning murakkabligini qanday baholash yoki…

Algoritmning murakkabligini baholash uchun asymptotik tahlil qo'llaniladi, bu algoritmning samaradorligini kirish ma'lumotlarining hajmiga ($n$) bog'liq ravishda tasvirlash imkonini beradi. Asosiy bosqichlar:

Asosiy operatsiyalarni aniqlash: $n$ ga sezgir bo'lgan operatsiyalar ajratiladi (masalan, solishtirishlar, tayinlashlar, arifmetik operatsiyalar).
Operatsiyalar sonini hisoblash: $n$ ga bog'liq bo'lgan asosiy operatsiyalar soni hisoblanadi. Bu aniq formula yoki baholash bo'lishi mumkin.
Asymptotik sinfni aniqlash: Kattaroq O ($O$), Omega ($\Omega$) va Teta ($\Theta$) belgilari yordamida yuqori, past va aniq asymptotik xatti-harakatlar tasvirlanadi.

$O(f(n))$: Algoritm $f(n)$ ga ko'paytirilgan konstant bilan chegaralangan va katta $n$ uchun amal qiladi. Bu "eng yomon" holat uchun ishlatiladi.
$\Omega(f(n))$: Algoritm $f(n)$ ga ko'paytirilgan konstant bilan kamida chegaralanadi va katta $n$ uchun amal qiladi. Bu "eng yaxshi" holat uchun ishlatiladi.
$\Theta(f(n))$: Algoritm $f(n)$ bilan proporsional bo'lgan va katta $n$ uchun amal qiladigan vaqt bilan chegaralanadi. Bu "o'rtacha" holat yoki eng yaxshi va eng yomon holatlar bir xil asymptotik tartibda bo'lsa ishlatiladi.

Eng ko'p ishlatiladigan Katta $O$ yuqori chegarani tasvirlash uchun, bu algoritmning yomon holatda qanday ishlashini tushunishda muhimdir.

Konstantlar va kichik a'zolarni e'tiborsiz qoldirish: Asymptotik aniqlashda konstant ko'paytuvchilar va past tartibli a'zolar e'tiborga olinmaydi, chunki katta $n$ uchun eng katta ko'rsatkichga ega funksiya ustun keladi. Masalan, $3n^2 + 5n + 10$ uchun asymptotik $O(n^2)$ bo'ladi.

Tipik asymptotik sinflar (murakkablik bo'yicha o'sish tartibida):

$O(1)$: Konstant murakkablik (vaqt $n$ ga bog'liq emas).
$O(\log n)$: Logarifmik murakkablik (vaqt juda sekin o'sadi, masalan, binar qidiruv algoritmi uchun).
$O(n)$: Chiziqli murakkablik (vaqt $n$ ga to'g'ri proporsional, masalan, oddiy tekshirish).
$O(n \log n)$: Chiziqli-logarifmik murakkablik (samara bilan ishlovchi sortlash algoritmlari uchun, masalan, Quick Sort yoki Merge Sort).
$O(n^2)$: Kvadrat murakkablik (vaqt $n^2$ ga o'sadi, masalan, Bubble Sort kabi oddiy sortlash algoritmlari uchun).
$O(n^c)$ (c > 1 uchun): Polinomiy murakkablik.
$O(c^n)$ (c > 1 uchun): Eksponential murakkablik (vaqt juda tez o'sadi, masalan, barcha mumkin bo'lgan variantlarni tekshirish uchun).
$O(n!)$: Faktoriyal murakkablik (eng yuqori sinf, juda tez o'sadi).

Tsiklik tuzilmalar uchun asymptotikani aniqlash:

Ketma-ket bloklar: Bloklarning murakkabligi yig'iladi. $O(A+B) = O(\max(A, B))$.
Ichma-ich sikllar: Iteratsiyalar soni ko'paytiriladi. $n$ iteratsiyali sikl ichida $m$ iteratsiyali sikl bo'lsa, $O(n \times m)$. Agar $m=n$, $O(n^2)$.
Input hajmi kamayadigan sikllar: Masalan, har iteratsiyada 2 ga bo'lish logarifmik murakkablikka olib keladi ($O(\log n)$).

Misol:

Oddiy massivni tekshirish:

# Asosiy operatsiyalarni hisoblash (solishtirishlar, tayinlashlar)
# Asosiy operatsiya - sikldagi solishtirish

def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 tayinlash (sikl tashqarisida)
    for i in range(1, len(arr)): # $n-1$ marta bajariladi
        # Siklda:
        # 1 solishtirish (if arr[i] > max_val)
        # ehtimol 1 tayinlash (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Agar massivning hajmi $n = \texttt{len(arr)}$, sikl $n-1$ marta bajariladi. Har bir iteratsiyada doimiy son operatsiyalar bajariladi. Umumiy operatsiyalar soni $n$ ga proporsional. Asymptotik murakkablik: $O(n)$.

Misol: Insertion Sort algoritmi

# Asosiy operatsiyalarni hisoblash
# Asosiy operatsiyalar: solishtirishlar va tayinlashlar

def insertion_sort(arr):
    # Tashqi sikl $n-1$ marta bajariladi
    for i in range(1, len(arr)):
        key = arr[i] # 1 tayinlash
        j = i - 1 # 1 tayinlash
        # Ichki sikl eng yomon holatda i marta bajariladi
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 tayinlash (harakat)
            j -= 1 # 1 ayirish va 1 tayinlash
        arr[j + 1] = key # 1 tayinlash

Tashqi sikl $n-1$ marta bajariladi. Ichki sikl eng yomon holatda (massiv teskari tartibda bo'lsa) har safar $i$ marta bajariladi. Barcha iteratsiyalar bo'yicha ichki sikl operatsiyalarining umumiy soni: $1 + 2 + ... + (n-1) \approx n^2/2$. Asymptotik murakkablik: $O(n^2)$ eng yomon va o'rtacha holatlar uchun, $O(n)$ eng yaxshi holatda (massiv allaqachon tartiblangan). Baholashda odatda eng yomon holat (Katta $O$) hisobga olinadi.

Algoritmning murakkabligini qanday baholash yoki uning asymptotasini qanday aniqlash mumkin?