Asymptotic Notations

Asimptotik belgilar — bu kiruvchi ma'lumotlar hajmi ma'lum bir qiymatga yoki cheksizlikka intilganda algoritmning ishlash vaqtini tavsiflash uchun ishlatiladigan matematik belgilardir.

Masalan: Bubble sort algoritmini olsak, agar kiruvchi massiv allaqachon saralangan bo'lsa, algoritm sarflagan vaqt chiziqli (linear) bo'ladi, ya'ni bu eng yaxshi holat (best case).

Ammo kiruvchi massiv teskari tartibda bo'lsa, algoritm elementlarni saralash uchun maksimal vaqt (kvadratik — quadratic) sarflaydi, ya'ni bu eng yomon holat (worst case).

Kiruvchi massiv saralangan ham, teskari tartibda ham bo'lmaganda, u o'rtacha vaqt sarflaydi. Ushbu davomiyliklar asimptotik belgilar yordamida ifodalanadi.

Asosan uchta asimptotik belgi mavjud:

• Big-O belgisi (Big-O notation)
• Omega belgisi (Omega notation)
• Theta belgisi (Theta notation)

Big-O belgisi

Big-O belgisi algoritm ishlash vaqtining yuqori chegarasini (upper bound) ifodalaydi. Shunday qilib, u algoritmning eng yomon holatdagi murakkabligini (worst-case complexity) beradi.

O(g(n)) = { f(n): musbat c va n0 konstantalari mavjud bo'lib, barcha n ≥ n0 uchun 0 ≤ f(n) ≤ c * g(n) shart bajariladi }

Yuqoridagi ifodani quyidagicha tushuntirish mumkin: agar yetarlicha katta n qiymatlari uchun 0 va c * g(n) oralig'ida yotadigan musbat c konstantasi mavjud bo'lsa, f(n) funksiyasi O(g(n)) to'plamiga tegishli bo'ladi.

n ning har qanday qiymati uchun algoritmning ishlash vaqti O(g(n)) tomonidan taqdim etilgan vaqtdan oshib ketmaydi.

U algoritmning eng yomon holatdagi ishlash vaqtini berganligi sababli, algoritmlarni tahlil qilishda keng qo'llaniladi, chunki bizni doimo eng yomon ssenariy qiziqtiradi.

Omega belgisi (Ω)

Omega belgisi algoritm ishlash vaqtining quyi chegarasini (lower bound) ifodalaydi. Shunday qilib, u algoritmning eng yaxshi holatdagi murakkabligini (best-case complexity) taqdim etadi.

Ω(g(n)) = { f(n): musbat c va n0 konstantalari mavjud bo'lib, barcha n ≥ n0 uchun 0 ≤ c * g(n) ≤ f(n) shart bajariladi }

Yuqoridagi ifodani quyidagicha tushuntirish mumkin: agar yetarlicha katta n qiymatlari uchun c * g(n) dan yuqorida yotadigan musbat c konstantasi mavjud bo'lsa, f(n) funksiyasi Ω(g(n)) to'plamiga tegishli bo'ladi.

n ning har qanday qiymati uchun algoritm talab qiladigan minimal vaqt Omega Ω(g(n)) bilan belgilanadi.

Theta belgisi (Θ)

Theta belgisi funksiyani yuqoridan va pastdan o'rab oladi. U algoritm ishlash vaqtining ham yuqori, ham quyi chegarasini ifodalaganligi sababli, algoritmning o'rtacha holatdagi murakkabligini (average-case complexity) tahlil qilish uchun ishlatiladi.

Biror g(n) funksiyasi uchun Θ(g(n)) quyidagi munosabat bilan aniqlanadi:

Θ(g(n)) = { f(n): musbat c1, c2 va n0 konstantalari mavjud bo'lib, barcha n ≥ n0 uchun 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) shart bajariladi }

Yuqoridagi ifodani quyidagicha tushuntirish mumkin: agar yetarlicha katta n qiymatlari uchun f(n) funksiyasi c1 * g(n) va c2 * g(n) oralig'ida joylashadigan musbat c1 va c2 konstantalari mavjud bo'lsa, u holda f(n) funksiyasi Θ(g(n)) to'plamiga tegishli bo'ladi.

Agar f(n) funksiyasi barcha n ≥ n0 uchun c1 * g(n) va c2 * g(n) oralig'ida yotsa, u holda f(n) asimptotik qat'iy chegara (asymptotically tight bound) deb ataladi.