Asosiy kontentga o‘tish
Informatik.uz
Bakalavr · 1-kurs2-bob. Dasturlash asoslari

Algoritm murakkabligi (Big-O)

Algoritmlarni solishtirish uchun ularning vaqt va xotira murakkabligi baholanadi. Big-O belgilashi, asosiy murakkablik sinflari va ularning katta ma’lumotlardagi farqini ko‘rib chiqamiz.

3-mavzu / 32 daq o‘qishYangilangan: 27-oktabr, 2026
Mavzular ro‘yxati (3 / 3)

1-bob. Axborot texnologiyalariga kirish

  1. 1Axborotni kodlash va ikkilik sanoq tizimi

Bir masalani turli algoritmlar bilan yechish mumkin, ularni solishtirish uchun murakkablik tushunchasi kiritiladi. Vaqt murakkabligi — kirish hajmi n ga bog‘liq holda algoritm bajaradigan elementar amallar soni, xotira murakkabligi esa qo‘shimcha ishlatiladigan xotira hajmidir. Soniyalar emas, amallar soni sanaladi, chunki ish vaqti kompyuterga va dasturlash tiliga bog‘liq bo‘ladi.

Big-O belgilashi funksiyaning o‘sish tartibini yuqoridan baholaydi. Rasmiy ta’rif: biror o‘zgarmas c > 0 va n0 topilib, barcha n ≥ n0 uchun f(n) ≤ c · g(n) bajarilsa, f(n) = O(g(n)) deyiladi. Amalda doimiy ko‘paytuvchilar va past tartibli hadlar tashlab yuboriladi: 3n + 5 = O(n), n² + 100n = O(n²). Odatda algoritmning eng yomon holati baholanadi.

Eng ko‘p uchraydigan murakkablik sinflari o‘sish tezligi bo‘yicha tartiblangan. O(1) — doimiy (masalan, a[i] elementga murojaat); O(log n) — logarifmik (ikkilik qidirish); O(n) — chiziqli (bitta sikl, masalan, for x in a: s += x); O(n log n) — samarali saralash (masalan, merge sort va Timsort); O(n²) — kvadratik (ichma-ich ikkita sikl, pufakchali saralash); O(2^n) — eksponentsial (n elementli to‘plamning barcha qism to‘plamlarini ko‘rib chiqish). Ketma-ket bajariladigan bloklarning murakkabligi qo‘shiladi va eng kattasi qoladi, ichma-ich sikllarniki esa ko‘paytiriladi.

Farq katta n larda sezilarli bo‘ladi. Kompyuter sekundiga taxminan 100 million oddiy amal bajaradi deb olsak, n = 1 000 000 uchun O(n) algoritm sekundning yuzdan bir ulushida, O(n log n) algoritm taxminan 0,2 soniyada, O(n²) algoritm esa taxminan 10 000 soniya, ya’ni qariyb 3 soat vaqt oladi. Shuning uchun katta ma’lumotlarda algoritmning murakkabligi qurilma tezligidan ko‘ra ko‘proq ta’sir qiladi.

Asosiy xulosalar

  • Murakkablik algoritm bajaradigan amallar sonining (yoki xotira hajmining) kirish hajmi n ga bog‘liqligini ifodalaydi.
  • Big-O o‘sish tartibini yuqoridan baholaydi; doimiy ko‘paytuvchilar va past tartibli hadlar tashlab yuboriladi.
  • Asosiy sinflar: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n) — o‘sish tezligi ortib boradi.
  • Ketma-ket bloklar murakkabligi qo‘shiladi, ichma-ich sikllarniki ko‘paytiriladi.
  • Katta n da murakkablik tartibi qurilma tezligidan ko‘ra ko‘proq ta’sir qiladi.

Amaliy topshiriqlar

  1. Quyidagi ifodalarni Big-O ko‘rinishiga keltiring: 5n + 20, n² + 3n + 7, 100, n log n + n, 2^n + n³.
  2. Quyidagi uchta parchaning vaqt murakkabligini aniqlang va izohlang: bitta sikl for i in range(n): s += i; ichma-ich ikkita sikl, ikkalasi ham range(n) bo‘yicha; sikl while i < n: i = i * 2 (boshida i = 1).
  3. Uzunligi n = 1000, 2000, 4000, 8000 bo‘lgan tasodifiy ro‘yxatlar uchun pufakchali saralash va o‘rnatilgan sorted() ishlash vaqtini time moduli bilan o‘lchang; vaqt qanday o‘sishini jadvalga yozib, nazariy murakkablik bilan solishtiring.

Mustahkamlash savollari

O‘zingizni sinab ko‘ring: avval o‘ylab ko‘ring, keyin javobni oching.

  1. 1Nima uchun Big-O belgilashida doimiy ko‘paytuvchilar tashlab yuboriladi?
    Katta n da o‘sish tartibi hal qiluvchi bo‘ladi, doimiy ko‘paytuvchi esa uni o‘zgartirmaydi va kompyuterga bog‘liq.
  2. 2Ketma-ket bajariladigan ikkita blokning murakkabligi O(n) va O(n²) bo‘lsa, umumiy murakkablik qanday?
    O(n + n²) = O(n²): eng katta had qoladi.
  3. 3n = 1000 bo‘lganda O(n²) va O(n log n) algoritmlar amallar soni bo‘yicha taxminan necha marta farq qiladi?
    n² = 1 000 000, n log2 n ≈ 10 000, ya’ni taxminan 100 marta.

0 / 3 mavzu o‘tildi

Kirib belgilash