2-bo‘lim
Samaradorlik va Big-O notatsiyasi
Algoritm tezligini o'lchash, murakkablik sinflari, Big-O notatsiyasini o'qish va xotira sarfini baholash.
Ushbu bo‘lim mundarijasi
- Nima uchun sekundomer yetarli emas?
- Big-O notatsiyasi
- Asosiy murakkablik sinflari
- Big-O ni hisoblash qoidalari
- 1-qoida: doimiylarni tashlab yuboring
- 2-qoida: eng tez o'sadigan hadni qoldiring
- 3-qoida: ichma-ich sikllar ko'paytiriladi
- 4-qoida: ketma-ket sikllar qo'shiladi
- Amaliy tahlil
- Xotira murakkabligi (Space Complexity)
- Eng yaxshi, o'rtacha va eng yomon holat
- Ma'lumotlar tuzilmalari taqqoslanishi
- Python amallarining murakkabligi
- Xulosa
O'tgan bo'limda bir masalaning ikki yechimi butunlay boshqa tezlikda ishlashini ko'rdik. Endi bu farqni o'lchashni o'rganamiz.
Nima uchun sekundomer yetarli emas? #
Tabiiy fikr: kodni ishga tushirib, vaqtini o'lchash. Lekin bu ishonchsiz:
| Muammo | Izoh |
|---|---|
| Kompyuterga bog'liq | Kuchli noutbukda tez, eski telefonda sekin |
| Tilga bog'liq | C dagi kod Python dagidan 50 barobar tez |
| Yukka bog'liq | Fon dasturlari natijani o'zgartiradi |
| Ma'lumot hajmiga bog'liq | 10 ta element uchun hammasi tez ishlaydi |
Bizga kompyuterga bog'liq bo'lmagan o'lchov kerak. Yechim - qadamlar sonini kirish hajmiga nisbatan hisoblash.
Big-O notatsiyasi #
Big-O algoritmning eng yomon holatdagi o'sish tezligini ko'rsatadi. n - kirish hajmi.
def birinchi_elementni_ol(royxat):
return royxat[0] # 1 ta amal, royxat qanchalik katta bo'lmasinBu O(1) - doimiy vaqt.
def yigindini_hisobla(royxat):
natija = 0
for element in royxat: # n marta takrorlanadi
natija += element
return natijaBu O(n) - chiziqli vaqt.
def barcha_juftliklar(royxat):
juftliklar = []
for birinchi in royxat: # n marta
for ikkinchi in royxat: # har biri uchun yana n marta
juftliklar.append((birinchi, ikkinchi))
return juftliklarBu O(n²) - kvadratik vaqt.
Asosiy murakkablik sinflari #
| Big-O | Nomi | Misol | n = 1000 da amallar |
|---|---|---|---|
| O(1) | Doimiy | Massiv elementiga murojaat | 1 |
| O(log n) | Logarifmik | Ikkilik qidiruv | ~10 |
| O(n) | Chiziqli | Ro'yxatni bir marta aylanish | 1 000 |
| O(n log n) | Chiziqli-logarifmik | Merge sort | ~10 000 |
| O(n²) | Kvadratik | Ichma-ich ikki sikl | 1 000 000 |
| O(n³) | Kubik | Uch sikl | 1 000 000 000 |
| O(2ⁿ) | Eksponensial | Rekursiv Fibonachchi | 10³⁰¹ |
| O(n!) | Faktorial | Barcha o'rin almashtirishlar | hisoblab bo'lmaydi |
Bir amal 1 nanosekund vaqt oladi deb faraz qilaylik. n = 50 bo'lganda:
| Murakkablik | Vaqt |
|---|---|
| O(n) | 50 nanosekund |
| O(n²) | 2.5 mikrosekund |
| O(2ⁿ) | 13 kun |
| O(n!) | Koinot yoshidan uzoqroq |
Shuning uchun eksponensial algoritm kichik kirishda ham yaroqsiz bo'lishi mumkin.
Big-O ni hisoblash qoidalari #
1-qoida: doimiylarni tashlab yuboring #
def misol(royxat):
print(royxat[0]) # O(1)
for element in royxat: # O(n)
print(element)
for element in royxat: # yana O(n)
print(element * 2)Jami: 1 + n + n = 2n + 1. Big-O da bu O(n).
Sabab: n juda katta bo'lganda 2n + 1 va n bir xil tezlikda o'sadi. Bizni o'sish shakli qiziqtiradi, aniq raqam emas.
2-qoida: eng tez o'sadigan hadni qoldiring #
n² + 5n + 100 → O(n²)
n = 1000 bo'lganda: 1 000 000 + 5 000 + 100. Birinchi had qolganlarini butunlay bosib ketadi.
3-qoida: ichma-ich sikllar ko'paytiriladi #
for i in range(n): # n
for j in range(n): # har biri uchun n
print(i, j) # jami n * nO(n²)
4-qoida: ketma-ket sikllar qo'shiladi #
for i in range(n): # n
print(i)
for j in range(m): # m
print(j)O(n + m) - agar n va m turli kattaliklar bo'lsa, ikkalasini ham yozing.
Amaliy tahlil #
def takrorlanuvchi_bormi_sekin(royxat):
"""Har bir juftlikni tekshiradi - O(n^2)."""
for i in range(len(royxat)):
for j in range(i + 1, len(royxat)):
if royxat[i] == royxat[j]:
return True
return False
def takrorlanuvchi_bormi_tez(royxat):
"""To'plamdan foydalanadi - O(n)."""
korilganlar = set()
for element in royxat:
if element in korilganlar:
return True
korilganlar.add(element)
return FalseIkkalasi ham to'g'ri javob beradi. Farqni o'lchab ko'ramiz:
import time
import random
sonlar = random.sample(range(1_000_000), 10_000)
for nomi, funksiya in [("Sekin O(n^2)", takrorlanuvchi_bormi_sekin),
("Tez O(n)", takrorlanuvchi_bormi_tez)]:
boshlanish = time.perf_counter()
funksiya(sonlar)
davomiylik = time.perf_counter() - boshlanish
print(f"{nomi:<16}{davomiylik:>8.4f} soniya")Sekin O(n^2) 2.8431 soniya
Tez O(n) 0.0009 soniya3000 barobar farq - va bu atigi 10 000 ta element uchun.
Xotira murakkabligi (Space Complexity) #
Vaqt yagona resurs emas. Algoritm qancha qo'shimcha xotira talab qilishi ham muhim.
def teskari_yangi_royxat(royxat):
"""O(n) qo'shimcha xotira - yangi ro'yxat yaratadi."""
natija = []
for element in reversed(royxat):
natija.append(element)
return natija
def teskari_joyida(royxat):
"""O(1) qo'shimcha xotira - asl ro'yxatni o'zgartiradi."""
chap, ong = 0, len(royxat) - 1
while chap < ong:
royxat[chap], royxat[ong] = royxat[ong], royxat[chap]
chap += 1
ong -= 1
return royxatKo'pincha tezlikni xotira hisobiga sotib olasiz. takrorlanuvchi_bormi_tez funksiyasi
O(n) qo'shimcha xotira (to'plam) sarflab, vaqtni O(n²) dan O(n) ga tushirdi.
Bu almashuv (trade-off) deb ataladi va deyarli har bir muhandislik qarorida uchraydi.
Eng yaxshi, o'rtacha va eng yomon holat #
def qidir(royxat, qidirilayotgan):
for indeks, element in enumerate(royxat):
if element == qidirilayotgan:
return indeks
return -1| Holat | Vaziyat | Murakkablik |
|---|---|---|
| Eng yaxshi (Ω) | Element birinchi o'rinda | O(1) |
| O'rtacha (Θ) | Element o'rtada | O(n/2) = O(n) |
| Eng yomon (O) | Element oxirida yoki yo'q | O(n) |
Amalda deyarli har doim eng yomon holat haqida gapiriladi - chunki dastur eng og'ir sharoitda ham ishlashi kerak.
Ma'lumotlar tuzilmalari taqqoslanishi #
Bu jadval butun darslik davomida sizga kerak bo'ladi:
| Tuzilma | Murojaat | Qidiruv | Qo'shish | O'chirish |
|---|---|---|---|---|
| Massiv (list) | O(1) | O(n) | O(n) | O(n) |
| Bog'langan ro'yxat | O(n) | O(n) | O(1) | O(1) |
| Stek | O(n) | O(n) | O(1) | O(1) |
| Navbat | O(n) | O(n) | O(1) | O(1) |
| Xesh-jadval | - | O(1)* | O(1)* | O(1)* |
| Ikkilik qidiruv daraxti | O(log n)* | O(log n)* | O(log n)* | O(log n)* |
* - o'rtacha holat. Eng yomon holatda xesh-jadval O(n), muvozanatsiz daraxt ham O(n) bo'lishi mumkin.
Python amallarining murakkabligi #
Ko'p dasturchi buni bilmaydi va bilmasdan sekin kod yozadi:
| Amal | Murakkablik | Izoh |
|---|---|---|
royxat[i] | O(1) | Indeks bo'yicha |
royxat.append(x) | O(1) | Oxiriga |
royxat.insert(0, x) | O(n) | Boshiga - hamma element suriladi |
royxat.pop() | O(1) | Oxiridan |
royxat.pop(0) | O(n) | Boshidan |
x in royxat | O(n) | Ketma-ket qidiradi |
x in toplam | O(1) | Xesh orqali |
x in lugat | O(1) | Xesh orqali |
lugat[k] | O(1) | Kalit bo'yicha |
sorted(royxat) | O(n log n) | Timsort |
len(royxat) | O(1) | Uzunlik saqlanadi |
# SEKIN - O(n^2), chunki har bir tekshiruv O(n)
natija = []
for element in katta_royxat:
if element not in natija:
natija.append(element)
# TEZ - O(n)
korilganlar = set()
natija = []
for element in katta_royxat:
if element not in korilganlar:
korilganlar.add(element)
natija.append(element)Quyidagi funksiyalarning Big-O murakkabligini aniqlang va sababini yozing:
def a(n):
return n * 2
def b(royxat):
for x in royxat:
for y in royxat:
for z in royxat:
print(x, y, z)
def c(n):
natija = 0
while n > 1:
n = n // 2
natija += 1
return natija
def d(royxat_1, royxat_2):
for x in royxat_1:
if x in royxat_2:
print(x)So'ng d funksiyasini O(n) ga optimallashtiring.
Xulosa #
- Big-O algoritmning kirish hajmi oshganda qanday o'sishini ko'rsatadi.
- Doimiylar va kichik hadlar tashlab yuboriladi:
3n² + 5n + 2→ O(n²). - Ichma-ich sikllar ko'paytiriladi, ketma-ket sikllar qo'shiladi.
- Odatda eng yomon holat hisobga olinadi.
- Xotira murakkabligi ham baholanishi kerak; tezlik va xotira o'rtasida almashuv bor.
inamali ro'yxatda O(n), to'plam va lug'atda O(1) - buni bilish kodni tez qiladi.
Keyingi bo'limda eng asosiy ma'lumotlar tuzilmasi - massiv bilan tanishamiz.
O‘qish tarixini saqlamoqchimisiz?
Tizimga kirsangiz, tugatgan bo‘limlaringiz saqlanadi va qoldirgan joyingizdan davom etasiz.
Xatolik topdingizmi?
Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.