Algoritmlar · Yechim vaqtga sig‘adimi? Kirish hajmiga qarab algoritm tanlash
Murakkablik
Medium
Nazariya
Murakkablik
Algoritm qancha vaqt va xotira olishini kirish hajmi n orqali baholaymiz. Bu O-belgisi
(«katta O») bilan yoziladi va kodni yozishdan oldin to‘g‘ri yo‘lni tanlashga yordam beradi.
Taxminiy jadval
Server sekundiga taxminan 10⁸ oddiy amal bajaradi. Vaqt chegarasi 1 sekund bo‘lsa:
| n gacha | Mos murakkablik | Misol |
|---|---|---|
| 10–20 | O(2ⁿ), O(n!) | barcha qism to‘plamlar, perestanovkalar |
| 500 | O(n³) | uch ichma-ich sikl |
| 5 000 | O(n²) | ikki ichma-ich sikl |
| 10⁵–10⁶ | O(n log n) | saralash, ikkilik qidiruv |
| 10⁷–10⁸ | O(n) | bitta o‘tish |
| 10¹⁸ | O(log n), O(1) | formula, ikkilik daraja |
Qanday sanash
for i in range(n): # n marta
for j in range(n): # har biriga n marta -> O(n²)
...
nums.sort() # O(n log n)
x in my_set # o‘rtacha O(1)
x in my_list # O(n) — katta siklda ehtiyot bo‘ling!
Diqqat
- Sikl ichida
list.index,in list, satr qo‘shish (s += ...) — yashirin O(n). - Python C++ dan ~10–50 marta sekin: chegaraga yaqin bo‘lsa, tezroq g‘oya izlang.
Ehtiyotkor bajarish
Ba’zi masalalarda maxsus algoritm kerak emas — shartni aniq va ehtiyotkorlik bilan bajarish kerak. Bunday masalalarda xato odatda chegaraviy holatlarda bo‘ladi.
Ish tartibi
- Shartni oxirigacha o‘qing, misollarni qo‘lda hisoblab ko‘ring.
- Barcha holatlarni ro‘yxat qiling: 0, 1, eng katta qiymat, teng qiymatlar, bo‘sh satr.
- Kodni kichik funksiyalarga bo‘ling — har birini alohida tekshirish oson.
def price(minutes):
if minutes <= 0:
return 0
hours = (minutes + 59) // 60 # yuqoriga yaxlitlash, float’siz
return min(hours * 3000, 20000) # kunlik chegara
Ko‘p uchraydigan xatolar
<va<=chalkashligi.- Yaxlitlash: yuqoriga yaxlitlash uchun
(a + b - 1) // b. - Chiqish formati: bo‘sh joy, qator oxiri, katta-kichik harf.
Bu kurs — faqat nazariya.