1. Algoritm murakkabligi
Muammo
Ikki dastur ham to‘g‘ri javob beradi, lekin biri 0,1 soniyada, ikkinchisi
40 daqiqada. Musobaqada ikkinchisi «Vaqt chegarasidan oshdi» oladi.
Demak, dasturni yozishdan oldin u qancha amal bajarishini
baholash kerak.
O-belgilash
Murakkablik — kirish hajmi n o‘sganda amallar soni qanday o‘sishi.
Doimiy ko‘paytuvchilar tashlanadi: muhimi o‘sish shakli.
| Belgi | Nomi | Misol |
|---|---|---|
| O(1) | doimiy | a[0], x + y |
| O(log n) | logarifmik | ikkilik qidiruv |
| O(n) | chiziqli | bitta sikl |
| O(n log n) | — | saralash |
| O(n²) | kvadratik | ichma-ich ikkita sikl |
| O(2ⁿ) | eksponensial | barcha kichik to‘plamlar |
10⁸ qoidasi
Bir soniyada taxminan 10⁸ oddiy amal bajariladi (Python‘da
kamroq — 10⁷ atrofida). Shundan kelib chiqib chegaraga qarab
algoritm tanlanadi:
| n | Mos murakkablik |
|---|---|
| n ≤ 10 | O(n!) ham bo‘ladi |
| n ≤ 20 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 5 000 | O(n²) |
| n ≤ 10⁶ | O(n log n) yoki O(n) |
| n ≤ 10⁹ | O(log n) yoki O(1) |
Masala shartidagi cheklovlar — bu maslahat. «n ≤ 200 000» deb
yozilgan bo‘lsa, O(n²) yechim ataylab kesib tashlanadi.
Qanday sanaladi
for i in range(n): # O(n)
for j in range(n): # ichida yana n
... # jami O(n²)Ketma-ket kelgan qismlar qo‘shiladi (O(n) + O(n log n) = O(n log n)),
ichma-ich kelganlar ko‘paytiriladi.
Xotira ham hisoblanadi
[0] * 10**9 — bu bir necha gigabayt. Xotira chegarasi ham masalada
yozilgan bo‘ladi.
Misol
# O(n) — bitta sikl
yigindi = 0
for x in a:
yigindi += x
# O(n^2) — ichma-ich
for i in range(n):
for j in range(n):
passMashq masalalari
| ✓ | Kod | Masala | Qiyinlik |
|---|---|---|---|
| AL01-1 | Gauss yig‘indisi | Boshlang‘ich | |
| AL01-2 | Teng juftliklar | Oson | |
| AL01-3 | Bo‘luvchilar soni | Oson | |
| AL01-4 | Kvadratlar oralig‘i | Oson | |
| AL01-5 | Birinchi takror | Oson |