Time complexity — algoritm bajarishi kerak bo‘lgan elementar amallar sonining kirish hajmiga bog‘liq o‘sishini ifodalovchi nazariy o‘lchovdir. U odatda sekundni emas, n kattalashganda ish miqdori qanday o‘zgarishini tahlil qiladi. Shu sabab turli apparat va dasturlash tilidagi algoritmlarni umumiy darajada taqqoslash mumkin.
Kirish hajmi
n nimani bildirishi muammoga bog‘liq: massiv elementlari, graph tugun va qirralari, sonning bit uzunligi yoki matn belgilaridir. Bir algoritm uchun bir nechta parametr kerak bo‘lishi mumkin. Graph traversal ko‘pincha O(V + E) bilan yoziladi.
Son qiymatini n deb olib, bit uzunligini unutish noto‘g‘ri natija beradi. Masalan, katta butun son ustidagi arifmetik amal doimiy vaqt emas; operand bitlari ko‘paygani sayin narx oshadi.
Holatlar
Worst-case complexity barcha bir xil hajmdagi kirishlar ichidagi eng katta ishni baholaydi. Average-case ma’lum input taqsimotiga bog‘liq o‘rtachani, best-case eng qulay holatni ko‘rsatadi. Amaliy kafolat kerak bo‘lsa worst-case ko‘proq ishlatiladi.
Amortized analysis operatsiyalar ketma-ketligidagi umumiy narxni taqsimlaydi. Dynamic array kengayishi ayrim appendda O(n), ammo ko‘p append bo‘yicha amortized O(1) bo‘ladi. Bu probabilistic average-case bilan bir xil tushuncha emas.
Asimptotik belgilash
Big O yuqori o‘sish chegarasini, Big Omega quyi, Big Theta esa tight boundni ifodalaydi. Constant koeffitsient va past darajali hadlar asimptotik yozuvda tashlanadi. 3n² + 5n + 2 uchun O(n²) deyiladi.
Bu constantlar ahamiyatsiz degani emas. Kichik inputda yaxshi cache locality’li O(n²) usul katta constantli O(n log n) usuldan tez bo‘lishi mumkin. Asimptotik tahlil va benchmark bir-birini to‘ldiradi.
Tahlil usuli
Ketma-ket bloklarning narxi qo‘shiladi, dominant had qoladi. Bir-birining ichidagi sikllar iteration soniga qarab ko‘payadi. Sikl har safar inputni yarmiga tushirsa logarithmic bosqich hosil bo‘ladi. Rekursiv algoritm uchun recurrence relation tuziladi.
Har ikki ichma-ich sikl avtomatik O(n²) emas. Ichki indeks tashqi indeksga bog‘liq bo‘lsa yig‘indi hisoblanadi; two-pointer usulida ichki pointer butun algoritm davomida jami n marta siljishi mumkin.
Amaliy omillar
Cache miss, branch prediction, allocation, I/O va parallelizm oddiy operation countda ko‘rinmaydi. External-memory algoritm disk block transfer sonini, distributed algoritm network round trip va xabar hajmini ham tahlil qiladi.
Real-time tizim average tezlikdan ko‘ra worst-case execution timega muhtoj. Input taqsimoti adversarial bo‘lsa hash collision yoki quicksort pivot tanlovi xavfga aylanadi. Complexity da’vosi model, input va holatni aniq ko‘rsatishi kerak.
Randomized algoritmlar
Random tanlov algoritm vaqtini ehtimollik o‘zgaruvchisiga aylantiradi. Randomized quicksort expected O(n log n) bo‘lsa-da, worst case O(n²) qoladi. Hash table amallari yaxshi hash va load factor ostida expected O(1), adversarial collisionda esa sekinlashishi mumkin. High-probability bound natija faqat o‘rtacha emas, katta ehtimol bilan chegarada qolishini ifodalaydi. Security kontekstida attacker inputni tanlashi mumkinligi sabab random seed, collision defense yoki deterministik worst-case kafolat ko‘rib chiqiladi.
Lower bound
Algoritmni yaxshilash chegarasini bilish uchun muammo modelidagi quyi bound isbotlanadi. Comparison sort barcha holatda Ω(n log n) taqqoslash talab qiladi. Counting sort bu boundni buzmaydi, chunki u faqat comparison modelida ishlamaydi va kalit diapazonidan foydalanadi. Modelni aniq aytish complexity da’vosining zarur qismidir.
Bog‘liq tushunchalar
Big O, Space complexity, Amortized analysis, Worst-case analysis, Algorithm, Recurrence relation