Algoritm va uning tezligi (Big-O)
Algoritm nima, qadamlarni sanash, O(1), O(n), O(n²), O(log n)
Algoritm — masalani yechish uchun aniq qadamlar ketma-ketligi. Ovqat retsepti ham algoritm: tartib bilan bajarilsa — natija bir xil.
Bitta masalaning bir nechta yechimi bo'lishi mumkin. Qaysi biri yaxshiroq? Odatda — ma'lumot ko'payganda qaysi biri tezroq ishlashi muhim. 10 ta element bilan hamma algoritm tez; 10 million bilan — farq soatlar bo'lishi mumkin.
Qadamlarni sanaymiz
Ro'yxatda takroriy element bormi? Ikki xil yechim:
def takror_bormi_1(r): # har juftni solishtirish
qadam = 0
for i in range(len(r)):
for j in range(i + 1, len(r)):
qadam += 1
if r[i] == r[j]:
return True, qadam
return False, qadam
def takror_bormi_2(r): # ko'rilganlarni to'plamda eslab qolish
korilgan = set()
qadam = 0
for x in r:
qadam += 1
if x in korilgan:
return True, qadam
korilgan.add(x)
return False, qadam
for n in [10, 100, 1000]:
r = list(range(n)) # takror yo'q — eng yomon holat
print(n, takror_bormi_1(r)[1], takror_bormi_2(r)[1])
# Natija: 10 45 10
# Natija: 100 4950 100
# Natija: 1000 499500 1000
Birinchisida qadamlar kvadrat bo'yicha o'sadi (n² / 2), ikkinchisida — chiziqli (n). 1000 ta elementda farq 500 barobar!
Big-O belgisi
Algoritm tezligini ma'lumot hajmi n ga nisbatan yozamiz — kichik detallar (½, +1) tashlab yuboriladi:
| Belgi | Nomi | Misol | n = 1 000 000 da taxminan |
|---|---|---|---|
| O(1) | o'zgarmas | ro'yxatdan r[5] olish, lug'atdan kalit |
1 qadam |
| O(log n) | logarifmik | ikkilik qidiruv (2-dars) | 20 qadam |
| O(n) | chiziqli | ro'yxatni bir marta aylanib chiqish | 1 mln qadam |
| O(n log n) | — | yaxshi saralash (sorted) |
20 mln qadam |
| O(n²) | kvadratik | har juftni solishtirish | 1 trln qadam — juda sekin |
💡 Yuqoridagi ikkinchi yechim tez, chunki
x in set— O(1),x in listesa — O(n). To'g'ri ma'lumot tuzilmasini tanlash — algoritmni tezlashtirishning eng oson yo'li.
Amaliyot Python
Ro'yxatdagi eng katta sonni bir marta aylanib (O(n)) toping — max() ishlatmang. Necha marta solishtirilganini ham chiqaring:
eng katta: 42, solishtirish: 5
input() uchun ma'lumotlar
Yechimni ko'rish
def eng_katta(r):
katta = r[0]
solishtirish = 0
for x in r[1:]:
solishtirish += 1
if x > katta:
katta = x
return f"eng katta: {katta}, solishtirish: {solishtirish}"
print(eng_katta([7, 42, 3, 19, 42, 8]))