Qo‘llanma · Dasturlash
complexity
Masalalar tez orada
Nazariya
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.
Bu mavzu bo‘yicha masalalar tez orada qo‘shiladi.